Solving algebraic problems over a ground field such as ℚ, considering only algebraic complexity (the number of base field operations) is hardly a good predictor of practical runtime: a precise analysis should take into account the size of the coefficients in the output, and the number of boolean operations throughout the execution of the algorithm.

One major challenge in such algorithms is the growth of coefficients. In many situations, we can give reasonably sharp a priori bounds on the bit size of the coefficients in the output SCSS 2024: 10th International Symposium on Symbolic Computation in Software Science, August 28-30, 2024, Tokyo, Japan Envelope jakellio@uwaterloo.ca (J. Elliott); eschost@uwaterloo.ca (É. Schost) GLOBE https://uwaterloo.ca/scholar/jakellio/home (J. Elliott); https://cs.uwaterloo.ca/~eschost/ (É. Schost) (a typical recipe being understanding them as determinants built from the input problem). Precisely, we will assume below that we know an upper bound 𝐻 on the height of all rational numbers appearing in the output, where in this note the height ℎ(𝑐) of a rational number 𝑐 is the maximum of the base-2 logarithms of the absolute values of its minimal numerator and denominator. However, such insight should not be expected for intermediate results of our algorithm. As the algorithm progresses, the size of these coefficients may increase, before possibly collapsing when we reach the end result.

Modular techniques are used to avoid intermediate expression swell. They involve performing computations modulo one or several small primes (ideally, machine primes), thereby avoiding intermediate coefficient growth, the objective being to compute the requested output (typically, a set of polynomials, or a matrix thereof) modulo a certain large integer 𝑀. If 𝑀 is large enough (precisely, if log 2 (𝑀) ≥ 𝐻 + 1), rational reconstruction can then be applied coefficient-wise, in order to recover an output with rational coefficients.

On one end of the spectrum, one can consider working modulo a single prime 𝑝, solve the problem modulo 𝑝 and lift the solution to ℤ/𝑀ℤ, for 𝑀 = 𝑝 𝑘 large enough, by means of Newton / Hensel techniques, if applicable. The obvious alternative is to compute modulo sufficiently many "small" primes (𝑝 𝑖 ) 1≤𝑖≤𝜂 and use the Chinese remainder theorem to obtain a solution modulo 𝑀 = 𝑝 1 ⋯ 𝑝 𝜂 .

For most problems of interest, there exist primes 𝑝 for which the procedure modulo 𝑝 is not well-defined, or returns a result that differs from the modulo 𝑝 reduction of the rational output; we will call these primes unlucky, and lucky otherwise. In the problems we have in mind, such as solving systems of polynomial equations, testing whether a prime is lucky may be prohibitively expensive. However, it is often possible to bound the number of unlucky primes: this is usually done by proving the existence of a nonzero 𝑈 ∈ ℤ such that all unlucky primes divide 𝑈, and bounding the height of 𝑈.

Using 𝑝-adic lifting techniques, we need to ensure that the initial prime 𝑝 is lucky; knowing the upper bound on 𝑈, we can determine what interval to pick 𝑝 from in order to guarantee a high probability of success, say at least 1 − 𝜀 for a given tolerance 𝜀. For Chinese remaindering algorithms, though, the direct approach requires all primes being lucky, and guaranteeing that this is the case with probability 1 − 𝜀 usually requires us to use larger primes (we discuss this further below). In this short note, we report on work-in-progress that uses error correction techniques (very loosely speaking, analogues of Reed-Solomon decoding, but for rational number reconstruction), where we tolerate that a few primes return wrong results (or no results at all). Our hope is then to be able to guarantee high probability of success, while using primes of moderate size.

We base our work on recent (independent) introductions of this idea, by Böhm, Decker, Fieker and Pfister [1,2] and Pernet [3], the former in the context of algorithms for algebraic geometry, and the latter mentioning applications to linear algebra. The decoding algorithms and the sufficient conditions for success given in these two families of references are distinct, but similar; both follow an iterative reduction procedure, stated as a variant of Euclid's algorithm in Pernet's work, and as a variant of Gaussian lattice reduction by Böhm et al. Our presentation will follows Pernet's.

The core of our discussion concerns the reconstruction of a single rational number. We also point out that in the contexts we are interested in, algorithms usually return several such numbers (typically as coefficients of polynomials), and we can often predict that all these rationals admit a small common denominator. Taking this specificity into account would lead us toward error-tolerant vector rational number reconstruction; ideally, we could hope to reduce the number of primes by up to two, but as of now, this appears to be quite challenging.

Let us first review the key result regarding Chinese remaindering for rational reconstruction in the presence of errors. We consider a sequence of prime moduli 𝑝 1 , … , 𝑝 𝜂 and a rational number 𝑟 = 𝑓 /𝑔, with 𝑔 > 0. The goal is to recover 𝑟 from a vector (𝑟 𝑖 ) 1≤𝑖≤𝜂 , where 𝑟 𝑖 = 𝑟 mod 𝑝 𝑖 for a certain number of lucky primes 𝑝 𝑖 . We tolerate a number of errors or missing values (e.g., for which 𝑝 𝑖 divides 𝑔), for which we write 𝑟 𝑖 = ∞, for a new symbol ∞; the corresponding primes are unlucky. Consider the following integers: Although these statements are well-established, to our knowledge, the following consequences, while relatively straightforward, are new. We provide a quantitative analysis which gives explicit sufficient conditions on the number of primes and their size to guarantee an arbitrary probability of success, in a model where we assume we can pick primes uniformly at random in a given interval.

Stating this result requires us to take all primes into consideration. Thus, 𝑟 and the upper bound 𝐻 are as above, and to each prime 𝑝 ∈ ℕ corresponds a value 𝑟(𝑝) (possibly ∞); 𝑝 is called lucky when 𝑟(𝑝) = 𝑟 mod 𝑝 and unlucky otherwise. We assume that there are finitely many unlucky primes and let 𝑈 be their product. In addition to the output size bound 𝐻, we then need a bound 𝐶 such that log 2 (𝑈 ) ≤ 𝐶. Both 𝐻 and 𝐶 are problem-dependent (we discuss a few examples in the next section); once bounds on 𝐻 and 𝐶 are available, the following propositions apply.

In what follows, for simplicity, given an interval Σ = {𝜎 , … , 2𝜎 }, we assume that we can sample 𝜂 primes in Σ uniformly without replacement, as long as this interval is known to contain at least 𝜂 primes. Proposition 1. Let 𝑟, 𝐻 , 𝐶 be as above. For 𝜖 > 0, let 𝜎 and 𝜂 be integers such that 𝜎 ≥ max(16, 16𝐶 𝜖 , 16𝐻 ) and 𝜂 = ⌈ 4𝐻 log 2 (𝜎) ⌉. Select pairwise distinct primes 𝑝 1 , … , 𝑝 𝜂 independently and uniformly at random from the set Σ = {𝜎 , … , 2𝜎 }. Then, with probability at least 1 − 𝜖, given (𝑟(𝑝 1 ), … , 𝑟(𝑝 𝜂 )), one can reconstruct 𝑟.

Proof. Let 𝒟 denote the set {𝑝 | 𝑝 ∈ Σ and 𝑈 mod 𝑝 = 0}, and notice that the product ∏ 𝑝∈𝒟 𝑝 also divides 𝑈, so that in particular ∏ 𝑝∈𝒟 𝑝 ≤ 𝑈. Each prime in Σ is at least equal to 𝜎, so that #𝒟 ≤ 𝐶 log 2 (𝜎) . On the other hand, the number of primes in Σ is at least 𝜎 2 log 2 (𝜎) [4,Ex. 18.18], so that for a prime 𝑝 chosen at random in Σ, ℙ(𝑝|𝑈 ) ≤

𝜎 . Now, we choose 𝜂 distinct primes 𝑝 1 , … , 𝑝 𝜂 uniformly at random in Σ, and for 𝑖 = 1, … , 𝜂, we let 𝑋 𝑖 be the indicator variable defined as

𝑋 𝑖 , so that 𝔼[𝑋 ] ≤ 2𝜂𝐶/𝜎. Now, for any choice of 𝜂 distinct primes (𝑝 𝑖 ) in Σ, the quantities 𝑁 and 𝐿 defined above satisfy 𝑁 = ∑ 𝜂 𝑖=1 log 2 (𝑝 𝑖 ) ≥ 𝜂 log 2 (𝜎 ) and 𝐿 = ∑ 1≤𝑖≤𝜂,𝑝 𝑖 unlucky prime log 2 (𝑝 𝑖 ) ≤ log 2 (2𝜎 )𝑋. From [3, Lemma 2.5.4] as cited above, we know that the error-tolerant rational reconstruction algorithm succeeds as soon as 𝐿 ≤ (𝑁 − 2𝐻 + 1)/2, and in particular as soon as log 2 (2𝜎 )𝑋 ≤ Δ = (𝜂 log 2 (𝜎) − 2𝐻 + 1)/2. We will point out below that for our choice of 𝜂, Δ is positive.

Then, the probability of failure is at most ℙ (log 2 (2𝜎 )𝑋 > Δ) = ℙ (𝑋 > Δ/ log 2 (2𝜎 )), which by Markov's inequality is at most 𝔼[𝑋 ]/ (Δ/ log 2 (2𝜎 )). We deduce

. Now, take 𝜂 = ⌈4𝐻/log 2 (𝜎 )⌉, so that in particular 𝜂 ≥ 4𝐻 /log 2 (𝜎 ), and thus 2𝐻 /(𝜂 log 2 (𝜎 )) ≤ 1/2, in which case the right-most factor in the inequality above is at most 2. Besides, this choices ensures Δ > 0. To summarize, in this case, we have ℙ(fail) ≤ 16𝐶/𝜎, and this can be made less than 𝜖 as soon as 𝜎 ≥ 16𝐶/𝜖. It remains to verify that our interval Σ contains at least 𝜂 primes. We know that there are at least 𝜎 /2 log 2 (𝜎 ) such primes, and that 𝜂 is at most 4𝐻 / log 2 (𝜎 ) + 1, and one checks that if 𝜎 ≥ 16 and 𝜎 ≥ 16𝐻, this is indeed less than or equal to 𝜎 /2 log 2 (𝜎 ).

In the context of a modular algorithm, the most important component in the cost analysis is the total time spent solving the problem modulo the primes 𝑝 𝑖 . In rough approximation, one can assume that each such execution takes 𝑇 operations modulo 𝑝 𝑖 , where 𝑇 is independent of 𝑖. It follows that the total boolean cost is softly-linear in 𝑇 ∑ 1≤𝑖≤𝜂 log 2 (𝑝 𝑖 ) ∈ Θ(𝑇 𝜂 log(𝜎 )).

In our construction, we have 𝜂 log 2 (𝜎 ) ≤ ( 4𝐻 log 2 (𝜎) + 1) log 2 (𝜎 ) = 4𝐻 + log 2 (𝜎 ). In other words, the boolean cost involves both the output size 𝐻, which is as expected, together with log 2 (𝜎 ), which will increase if we take 𝜖 close to zero. Remark 3. Assume that we do not use error-correction. In this case, in order to be able to reconstruct 𝑟, we need all primes to be lucky. With notation as in the proposition, we saw that the probability that a single prime is unlucky is at most 2𝐶/𝜎, so when choosing 𝜂 primes, the probability that at least one of them is unlucky is at most

Assuming we choose 𝜂 as above, let us derive a bound on 𝜎 that ensures 2𝜂𝐶/𝜎 < 𝜖. We proceed informally and take 𝜂 = 4𝐻/log 2 (𝜎 ), so our inequality is satisfied when 8𝐶𝐻/(𝜎 log 2 (𝜎 )) < 𝜖.

Hence we require that 𝜎 log 2 (𝜎 ) ≥ 8𝐻 𝐶/𝜖; this gives 𝜎 ≥ 𝑅(8𝐻 𝐶/𝜖), where 𝑅 is the reciprocal function of 𝑥 ↦ 𝑥 log 2 (𝑥). This function grows like 𝑥/ ln(𝑥), for 𝑥 → ∞, which gives asymptotically 𝜎 ≥ 8𝐻 𝐶/(𝜖 ln(8𝐻 𝐶/𝜖)). As expected, this is inferior to the bound given in the previous proposition.

We end this note with a quick description of possible use cases of this work.

. In [5], Storjohann gives a modular algorithm to compute Hermite forms for matrices with entries in ℚ[𝑥], together with bounds 𝐻 on the output size and 𝐶 on the unlucky primes. Our work applies directly to this situation. We are not aware of alternative methods that would rely on Newton iteration.

Computing lexicographic Gröbner bases in ℚ[𝑥, 𝑦]. In [6], St-Pierre and Schost provide similar bounds 𝐻 and 𝐶 for the computation of bivariate Gröbner bases; again, our work applies directly. In this case, an alternative approach based on Newton iteration exists, but has rather high complexity.

Solving zero-dimensional systems in ℚ[𝑥 1 , … , 𝑥 𝑛 ]. The main application we have in mind is the solution of zero-dimensional polynomial systems (by means of a data-structure known as a zero-dimensional parametrization, see [7] for a definition and references). When the complex solutions have multiplicity one, a simple form of Newton iteration is applicable [8], but without this assumption, lifting techniques are complex to analyze. In this case, a bound 𝐻 on the output size is available by means of the arithmetic Bézout theorem, but the unlucky primes are harder to describe. The reference [9] quantifies primes 𝑝 for which the number of solutions changes modulo 𝑝, but further arguments are needed to control other possible degeneracies.