mathlib3 documentation


A norm_num extension for Jacobi and Legendre symbols #

THIS FILE IS SYNCHRONIZED WITH MATHLIB4. Any changes to this file require a corresponding PR to mathlib4.

We extend the tactic.interactive.norm_num tactic so that it can be used to provably compute the value of the Jacobi symbol J(a | b) or the Legendre symbol legendre_sym p a when the arguments are numerals.

Implementation notes #

We use the Law of Quadratic Reciprocity for the Jacobi symbol to compute the value of J(a | b) efficiently, roughly comparable in effort with the euclidean algorithm for the computation of the gcd of a and b. More precisely, the computation is done in the following steps.

We provide customized versions of these results for the various reduction steps, where we encode the residue classes mod 2, mod 4, or mod 8 by using terms like bit1 (bit0 a). In this way, the only divisions we have to compute and prove are the ones occurring in the use of QR above.

The Jacobi symbol restricted to natural numbers in both arguments.


API Lemmas #

We repeat part of the API for jacobi_sym with norm_num.jacobi_sym_nat and without implicit arguments, in a form that is suitable for constructing proofs in norm_num.

Base cases: b = 0, b = 1, a = 0, a = 1.

theorem norm_num.legendre_sym.to_jacobi_sym (p : ) (pp : fact ( p)) (a r : ) (hr : jacobi_sym a p = r) :

Turn a Legendre symbol into a Jacobi symbol.

theorem norm_num.jacobi_sym.mod_left (a : ) (b ab' : ) (ab r b' : ) (hb' : b = b') (hab : a % b' = ab) (h : ab' = ab) (hr : norm_num.jacobi_sym_nat ab' b = r) :

The value depends only on the residue class of a mod b.

theorem norm_num.jacobi_sym_nat.mod_left (a b ab : ) (r : ) (hab : a % b = ab) (hr : norm_num.jacobi_sym_nat ab b = r) :
theorem norm_num.jacobi_sym_nat.even_even (a b : ) (hb₀ : b 0) :

The symbol vanishes when both entries are even (and b ≠ 0).

When a is odd and b is even, we can replace b by b / 2.

If a is divisible by 4 and b is odd, then we can remove the factor 4 from a.

If a is even and b is odd, then we can remove a factor 2 from a, but we may have to change the sign, depending on b % 8. We give one version for each of the four odd residue classes mod 8.

Use quadratic reciproity to reduce to smaller b.

theorem norm_num.jacobi_sym_nat.qr₁_mod (a b ab : ) (r : ) (hab : bit1 b % bit1 (bit0 a) = ab) (hr : norm_num.jacobi_sym_nat ab (bit1 (bit0 a)) = r) :
theorem norm_num.jacobi_sym_nat.qr₁'_mod (a b ab : ) (r : ) (hab : bit1 (bit0 b) % bit1 a = ab) (hr : norm_num.jacobi_sym_nat ab (bit1 a) = r) :
theorem norm_num.jacobi_sym_nat.qr₃_mod (a b ab : ) (r : ) (hab : bit1 (bit1 b) % bit1 (bit1 a) = ab) (hr : norm_num.jacobi_sym_nat ab (bit1 (bit1 a)) = r) :

Certified evaluation of the Jacobi symbol #

The following functions recursively evaluate a Jacobi symbol and construct the corresponding proof term.

This evaluates r := jacobi_sym_nat a b recursively using quadratic reciprocity and produces a proof term for the equality, assuming that a < b and b is odd.

This evaluates r := jacobi_sym_nat a b and produces a proof term for the equality by removing powers of 2 from b and then calling prove_jacobi_sym_odd.

This evaluates r := jacobi_sym a b and produces a proof term for the equality. This is done by reducing to r := jacobi_sym_nat (a % b) b.

The norm_num plug-in #

This is the norm_num plug-in that evaluates Jacobi and Legendre symbols.