CS Paper Radar

Parallel Integration over Simple Radical Extensions III: Antiderivatives in Terms of Special Functions

Sam Blake

cs.SC ·submitted 2026-10-03 12:27 UTC · v1
theory

Abstract

We extend the parallel integration method for mixed towers of Part~II from elementary antiderivatives to antiderivatives in special functions. The class covered is the incomplete gamma function $Γ(s,\cdot)$ at rational $s$, which contains $\Ei$, $\li$, $\Si$, $\Ci$, $\erf$ and the Fresnel integrals, together with the elliptic integrals $F$, $E$, $Π$. Each special function enters through a \emph{kernel}: a known element of the tower whose antiderivative is that function. It is either fixed by residues or added as one more column of the single linear system, and no Risch differential equation is solved. We prove where kernels can have poles; the $\erf$ kernels live in the sub-critical window of radical towers. The denominator theory, degree bounds and certificates of Part~II carry over, and new criteria decide most places that Part~II leaves to a guess. Elliptic integrals are carried by the radical, and a non-torsion residue divisor becomes a third-kind term. We prove that special functions are introduced only when necessary. Elementary answers are returned unchanged, and in strict mode a special function comes with a certificate that the integrand has no elementary integral. When no complete answer is found, a partial answer with a reduced remainder is returned. All examples are computed by a SymPy implementation and verified by differentiation.

Closest papers

Nearest neighbours by meaning across the whole index.

Parallel Integration over Simple Radical Extensions

cs.SC ·2026-08-30 ·Sam Blake
theory similarity 0.70
Abstract

The parallel Risch (Risch--Norman) method is a fast heuristic for computing elementary integrals over towers of transcendental extensions. Its justification rests on two structural facts about the integral: a bound on its denominator and a description of the logarithms that can occur. Both are known for purely logarithmic towers (Davenport--Trager) and, in the form of a structure theorem, for arbitrary derivations on multivariate rational function fields (Bronstein). We extend both facts to a simple radical extension $L=K(y)$, $y^m=q$, of such a field. The key observations are that the integral closure of $F[t_1,\dots,t_n]$ in $L$ has an explicit basis, so that all factorisation can remain in a polynomial ring, and that the derivation has a well-defined pole order $δ_P\in\{0,1,e_P\}$ at every height-one prime $P$, so that pole orders of derivatives shift by $δ_P$. The denominator of the integral then has the same Hermite-type shape as in the transcendental case, while the admissible logands are precisely the $S$-units of the integral closure for an explicit finite set $S$ of primes; the latter can be larger than the set generated by irreducible polynomials, as the unit $x+\sqrt{x^2+1}$ shows. For $n=1$ we relate these $S$-units to torsion in the Jacobian and, for $m=2$, to the polynomial Pell equation, obtaining a complete description of the logarithmic part in genus~0. We describe the resulting algorithm and give examples.

0.46

Parallel Integration over Simple Radical Extensions in Mixed Towers: Charlwood's Integrals

cs.SC ·2026-09-22 ·Sam Blake
similarity 0.62
Abstract

We evaluate a SymPy implementation of the parallel Risch-Norman method using Charlwood's 2008 suite of 50 challenging indefinite integrals. The system automatically builds integrand towers, verifies answers by differentiation, and returns correct, verified integrals for 49 problems with zero errors. The single failure, $\int\arcsin(x\sqrt{1-x^2})\,dx$, is proven non-elementary using a holomorphic-remainder certificate, though limited by an unverified completeness hypothesis on a genus-three curve. Part II's degree bounds successfully reduce classical ansatz sizes by two-thirds without impacting running time. The paper details algorithmic mechanisms like $S'$-units, Pell units, and residue computing in tower coordinates. Compared to mature implementations, this untuned SymPy prototype is slower than FriCAS (by a factor of six on the median integral) but more accurate than AXIOM (which returned three wrong answers). Profiling pinpoints performance bottlenecks in nonlinear norm searches and nested number fields, outlining clear targets for optimisation.

0.39

Parallel Integration over Simple Radical Extensions II: Mixed Towers

cs.SC ·2026-09-12 ·Sam Blake
theory similarity 0.61
Abstract

In Part I we extended the structure theorems underlying the Risch--Norman (parallel Risch) method to a simple radical extension $L=K(y)$, $y^m=q$, of a differential field $K=F(t_1,\dots,t_n)$ closed under the derivation. Here we remove the closure hypothesis: the radical may occupy any position in the tower, so that the derivatives of the generators above it involve $y$ --- the setting of Bronstein's algorithm for mixed elementary functions. The working ring is $\cA=\cO[t_{j+1},\dots,t_n]$, the integral closure of $F[t_1,\dots,t_n]$ in $L$: a Krull domain, free over the polynomial ring on Trager's basis, so that all factorisation remains in a unique factorisation domain. The denominator of the derivation is no longer an element but a divisor $\fd_D$ on $\cA$, and the valuation lemma takes the unified form $v_P(Dg)=v_P(g)-(1+v_P(\fd_D))$ at normal height-one primes, subsuming the shifts $\{1,e_P\}$ of Part I; the proof localises and requires no cancellation analysis. Stability of the class group and the unit group, $\Cl(\cA)\cong\Cl(\cO)$ and $\cA^*=\cO^*$, splits the admissible logands into $S$-units of $\cO$ --- computed by the machinery of Part I --- and irreducible polynomials moving in the upper variables, whose residues must be constants. We prove degree bounds in the top variable and describe the resulting algorithm, which --- unlike the classical parallel method, whose failure proves nothing --- returns certificates of non-elementarity in two situations: a residue outside the constant field, and, when every bound in force is proved, a residue-free remainder that the linear system shows to be non-exact.

0.27

An Infinite Family of Apéry-like Recurrences for Euler's Constant

cs.SC math.NT ·2026-10-09 ·Rotem Kalisch, Tali Monderer, Elyasheev Leibtag, Shachar Weinbaum, Michael Shalyt +1 more
unusual similarity 0.44
Abstract

Euler's constant $γ$, also known as the Euler-Mascheroni constant, remains one of the most elusive constants in mathematics. Despite extensive study, its irrationality is still unproven, and Apéry-like approximations of it are remarkably scarce. We present a novel identity that expresses $γ$ in terms of a Meijer G-function and its first few derivatives. This identity is then generalized and used to systematically generate infinitely many Apéry-like approximations of $γ$ using a Conservative Matrix Field construction based on the Meijer G-function.

0.27

Supersingular Elliptic Curves Without Inseparable Small Degree Endomorphisms

cs.CR math.NT ·2026-09-03 ·Nicolas Swanson
theorycode/dataunusual similarity 0.41
Abstract · Computational supplement available at https://github.com/Nicswansonwaterloo/MaxFrobeniusConj

For a fixed characteristic $p$, let $δ(p)$ denote the smallest degree needed to guarantee the existence of an isogeny from any supersingular curve $E$ to its Frobenius conjugate $E^{(p)}$. We translate existence questions concerning $δ(p)$ into questions about positive definite integral ternary quadratic forms and use Voronoi's theory of perfect forms in dimension three to characterize when $δ(p)$ is nearly maximal. For sufficiently large primes, we show that $δ(p)$ attains its upper bound precisely when $p$ is represented by one of nine explicit cubic polynomials, reducing the infinitude of such primes to whether one of these cubics takes prime values infinitely often. We also prove that, for almost all primes, $δ(p)$ lies at least $p^{1/6-o(1)}$ below its upper bound.

0.68

New Construction of Power Functions with Low c-Differential Uniformity over Finite Fields

cs.IT ·2026-09-19 ·Zhiye Yang, Yan Wang, Keqin Feng
theory similarity 0.38
Abstract

This paper investigates the $c$-differential uniformity of power functions over finite fields, an important class of cryptographic functions with favorable differential properties. Specifically, for finite fields $\mathbb{F}_q$ satisfying $q-1=en$ with $e\ge 3$ and $e\mid n$, we prove that there exists $c\in\mathbb{F}_q\setminus\{0,1,ε,\dots,ε^{e-1}\}$, where $ε$ is an $e$-th primitive root of unity in $\mathbb{F}_q^*$, the constructed power functions $f(x)=x^{ln+1}$ with $1\le l\le e-1$ and $\gcd(l,e)=1$ satisfy the upper bound $Δ(f,c)\le e$, provided that certain cyclotomic conditions hold. We show that our conditions are mild; namely, such power functions can be constructed over infinitely many extension fields $\mathbb{F}_q$ of $\mathbb{F}_p$ for any given $e\ge 3$ and prime $p$ with $p\nmid e$. Furthermore, based on the Weil bound for multiplicative character sums, we prove that the obtained upper bound is tight for sufficiently large $q$, demonstrating the optimality of our results. We also analyze the special case $c=-1$ and derive simplified explicit conditions. In particular, we explicitly characterize the admissible parameters for the case $e=3$ and present concrete function examples for practical validation.

0.25

Ramanujan quantum expanders from the Weil representation

cs.CC quant-ph ·2026-09-29 ·Siddhartha Jain
similarity 0.38
Abstract

For every odd prime power $q$ and $D=q+1$, we construct an infinite family of Ramanujan quantum expanders of degree $D$. The construction transfers Morgenstern's Ramanujan Cayley graphs on $\operatorname{PSL}_2(\mathbb{F}_{p})$ for $p$ which is an even power of $q$, through the odd irreducible subrepresentation of the Weil representation of $\operatorname{SL}_2(\mathbb{F}_{p})$. For a quantum expander of dimension $N$, our implementation uses $O(\log^2 N)$ elementary gates, and $O(\log N)$ ancilla qudits, using a fixed finite gate set depending on $q$. An advantage compared to the previous work of Iyer, Jain, Jordan, and Somma (FOCS 2026) is that assuming the quantum circuit is implemented exactly, we satisfy the $2\sqrt{D-1}/D$ singular value bound exactly without any additive error.

0.27

Deterministic Root-Finding over Finite Fields with Elliptic Curves

cs.SC cs.CCmath.NT ·2026-10-23 ·Pierre-Jean Spaenlehauer
similarity 0.38
Abstract

Finding the roots of a polynomial over a finite field $\mathbb F_q$ in deterministic polynomial time is a long-standing open problem. Classical deterministic methods work in the multiplicative group $\mathbb F_q^\times$ and are efficient only when $q-1$ is smooth, which is rarely the case. We propose a method that replaces $\mathbb F_q^\times$ by the groups of rational points of an elliptic curve $E$ and of its quadratic twist $\widetilde E$. The computation splits into an offline phase, which depends only on $\mathbb F_q$ and outputs a short \emph{elliptic preprocessing datum} $\mathcal D$, and an online phase, which processes the input polynomial. Writing $Ξ(\mathcal D)$ for the largest prime factor of $\lvert E(\mathbb F_q)\rvert\cdot\lvert\widetilde E(\mathbb F_q)\rvert$, the online phase is deterministic and finds the roots of any $f\in\mathbb F_q[X]$ of degree $n$ within $\widetilde O(Ξ(\mathcal D)^2\,n\log^2 q+n^ω\log q+n\log^3 q)$ operations in $\mathbb F_q$. A precursor of our method is an algorithm by Rónyai, which recovers the roots through Galois computations over number fields, relies on GRH, and comes with a polynomial bound of unspecified degree; in contrast, our online phase works entirely over $\mathbb F_q$ and is unconditional. Moreover, $\mathcal D$ can be certified deterministically and unconditionally in time polynomial in $\log q$ and $Ξ(\mathcal D)$. We conjecture that every $\mathbb F_q$ of large enough characteristic admits a datum with $Ξ(\mathcal D)\leq(\log q)^{O(1)}$, and support this with a heuristic and with experiments. Constructing such a datum in polynomial time remains open.

0.22