The discovery of formulas involving mathematical constants such as $\pi$ and $e$ had a great impact on various fields of science and mathematics. However, such discoveries have remained scarce, relying on the intuition of mathematicians such as Ramanujan and Gauss. Recent efforts to automate such discoveries, such as the Ramanujan Machine project, relied solely on exhaustive search and remain limited by the space of options that can be covered. Here we propose a fundamentally different method to search for conjectures on mathematical constants: through analysis of integer sequences. We introduce the Enumerated Signed-continued-fraction Massey Approve (ESMA) algorithm, which builds on the Berlekamp-Massey algorithm to identify patterns in integer sequences that represent mathematical constants. ESMA has found various known formulas and new conjectures for $e, e^2, \tan(1)$, and ratios of values of Bessel functions, many of which provide faster numerical convergence than their corresponding simple continued fractions forms. We also characterize the space of constants that ESMA can catch and quantify its algorithmic advantage in certain scenarios. Altogether, this work continues the development toward algorithm-augmented mathematical intuition, to help accelerate mathematical research.

Given disjoint sets S , S' ⊆ 𝔽 q of size n and a function f : S → 𝔽 q , where 𝔽 q is a finite field, the low-degree extension (LDE) of f to S' is the function f ' : S ' → 𝔽 q obtained by restricting the interpolating polynomial of f to S' . LDE computation is a fundamental primitive of modern algebraic coding theory and cryptography. The best asymptotic running time for LDE with parameter n is O(n log n ) arithmetic operations over 𝔽 q - when q and the sets S, S' are special. This running time is achieved via the Fast Fourier Transform (FFT), and requires 𝔽 q to contain a multiplicative subgroup of smooth order ≥ n (smoothness means being the product of small primes). Another variant uses an additive subgroup of smooth order ≥ n . Most finite fields do not contain such a subgroup, which raises the question of computing the LDE in time O(n · log n ) over general finite fields, for some disjoint pair of sets S , S ' of size n . The main result of this paper is a positive answer to this question, presenting O(n log n )-time LDE for special S , S ' shown to exist over all fields, as long as q = Ω( n 2 ). This result is achieved by introducing a new FFT-like transform, the Elliptic Curve Fast Fourier Transform (ECFFT), which gives an approach to fast algorithms (using preprocessing) for polynomial operations over all large finite fields. The key idea is to replace the group of roots of unity with a set of points L ⊂ 𝔽 q suitably related to a well-chosen elliptic curve group over 𝔽 q (the set L itself is not a group). The key advantage of this approach is that elliptic curve groups can be of any size in the Hasse-Weil interval and thus can have subgroups of large, smooth order, which an FFT-like divide and conquer algorithm can exploit. Compare this with multiplicative subgroups over 𝔽 q whose order must divide q − 1. By analogy, our method extends the standard, multiplicative FFT in a similar way to how Lenstra's elliptic curve method [Len87] extended Pollard's p − 1 algorithm [Pol74] for factoring integers. Representing polynomials by their evaluation over (well-chosen) subsets of L , we use the ECFFT to compute the LDE in time O(n log n ). We also give small arithmetic circuits for polynomial multiplication, division, degree-computation, interpolation, evaluation and Reed-Solomon encoding (also known as low-degree extension) with fixed evaluation points , matching the circuit size of classical FFT-based algorithms when the field size q is special. For the classical problems (in the standard representation) of low degree extension with chosen evaluation points, and evaluating elementary symmetric polynomials, this yields the asymptotically smallest known arithmetic circuits. The efficiency of the classical FFT follows from using the 2-to-1 squaring map to reduce the evaluation set of roots of unity of order 2 k to similar groups of size 2 k-i , i > 0. Our algorithms operate similarly, using isogenies of elliptic curves with kernel size 2 as 2-to-1 maps to reduce L of size 2 k to sets of size 2 k-i that are, like L , suitably related to elliptic curves, albeit different ones.

A collection of sets displays a proximity gap with respect to some property if for every set in the collection, either (i) all members are δ-close to the property in relative Hamming distance or (ii) only a tiny fraction of members are δ-close to the property. In particular, no set in the collection has roughly half of its members δ-close to the property and the others δ-far from it. We show that the collection of affine spaces displays a proximity gap with respect to Reed-Solomon (RS) codes, even over small fields, of size polynomial in the dimension of the code, and the gap applies to any δ smaller than the Johnson/Guruswami-Sudan list-decoding bound of the RS code. We also show near-optimal gap results, over fields of (at least) linear size in the RS code dimension, for δ smaller than the unique decoding radius. Concretely, if δ is smaller than half the minimal distance of an RS code V ⊂ Fqn, every affine space is either entirely δ-close to the code, or alternatively at most an ( n/q)-fraction of it is δ-close to the code. Finally, we discuss several applications of our proximity gap results to distributed storage, multi-party cryptographic protocols, and concretely efficient proof systems. We prove the proximity gap results by analyzing the execution of classical algebraic decoding algorithms for Reed-Solomon codes (due to Berlekamp-Welch and Guruswami-Sudan) on a formal element of an affine space. This involves working with Reed-Solomon codes whose base field is an (infinite) rational function field. Our proofs are obtained by developing an extension (to function fields) of a strategy of Arora and Sudan for analyzing low-degree tests.