mathlib docs: data.zsqrtd.basic

data.zsqrtd.basic

zsqrtd.add_comm_monoid

zsqrtd.add_comm_semigroup

zsqrtd.add_le_add_left

zsqrtd.add_lt_add_left

zsqrtd.add_monoid

zsqrtd.add_semigroup

zsqrtd.char_zero

zsqrtd.coe_int_add

zsqrtd.coe_int_im

zsqrtd.coe_int_inj

zsqrtd.coe_int_mul

zsqrtd.coe_int_re

zsqrtd.coe_int_sub

zsqrtd.coe_int_val

zsqrtd.coe_nat_im

zsqrtd.coe_nat_re

zsqrtd.coe_nat_val

zsqrtd.comm_monoid

zsqrtd.comm_ring

zsqrtd.comm_semigroup

zsqrtd.comm_semiring

zsqrtd.conj_mul

zsqrtd.decidable_eq

zsqrtd.decidable_le

zsqrtd.decidable_linear_order

zsqrtd.decidable_linear_ordered_comm_ring

zsqrtd.decidable_linear_ordered_semiring

zsqrtd.decidable_nonneg

zsqrtd.decidable_nonnegg

zsqrtd.decompose

zsqrtd.divides_sq_eq_zero

zsqrtd.divides_sq_eq_zero_z

zsqrtd.eq_zero_or_eq_zero_of_mul_eq_zero

zsqrtd.has_zero

zsqrtd.inhabited

zsqrtd.integral_domain

zsqrtd.is_monoid_hom

zsqrtd.le_antisymm

zsqrtd.le_of_add_le_add_left

zsqrtd.le_of_le_le

zsqrtd.le_total

zsqrtd.le_trans

zsqrtd.linear_ordered_semiring

zsqrtd.mul_conj

zsqrtd.mul_nonneg

zsqrtd.muld_val

zsqrtd.nonneg_add

zsqrtd.nonneg_add_lem

zsqrtd.nonneg_antisymm

zsqrtd.nonneg_cases

zsqrtd.nonneg_iff_zero_le

zsqrtd.nonneg_mul

zsqrtd.nonneg_mul_lem

zsqrtd.nonneg_muld

zsqrtd.nonneg_smul

zsqrtd.nonneg_total

zsqrtd.nonnegg_cases_left

zsqrtd.nonnegg_cases_right

zsqrtd.nonnegg_comm

zsqrtd.nonnegg_neg_pos

zsqrtd.nonnegg_pos_neg

zsqrtd.nonsquare

zsqrtd.nontrivial

zsqrtd.norm_eq_mul_conj

zsqrtd.norm_eq_one_iff

zsqrtd.norm_int_cast

zsqrtd.norm_mul

zsqrtd.norm_nat_cast

zsqrtd.norm_nonneg

zsqrtd.norm_one

zsqrtd.norm_zero

zsqrtd.not_divides_square

zsqrtd.not_sq_le_succ

zsqrtd.of_int_eq_coe

zsqrtd.of_int_im

zsqrtd.of_int_re

zsqrtd.ordered_semiring

zsqrtd.preorder

zsqrtd.semigroup

zsqrtd.semiring

zsqrtd.smul_val

zsqrtd.smuld_val

zsqrtd.sq_le_add

zsqrtd.sq_le_add_mixed

zsqrtd.sq_le_cancel

zsqrtd.sq_le_mul

zsqrtd.sq_le_of_le

zsqrtd.sq_le_smul

zsqrtd.sqrtd_im

zsqrtd.sqrtd_re

structure zsqrtd :

ℤ → Type

re : ℤ
im : ℤ

The ring of integers adjoined with a square root of d. These have the form a + b √d where a b : ℤ. The components are called re and im by analogy to the negative d case, but of course both parts are real here since d is nonnegative.

@[instance]

def zsqrtd.decidable_eq {d : ℤ} :

decidable_eq (ℤ√d)

Equations

zsqrtd.decidable_eq = id (λ (_v : ℤ√d), _v.cases_on (λ (re im : ℤ) (w : ℤ√d), w.cases_on (λ (w_re w_im : ℤ), decidable.by_cases (λ (a : re = w_re), eq.rec (decidable.by_cases (λ (a : im = w_im), eq.rec (decidable.is_true _) a) (λ (a : ¬im = w_im), decidable.is_false _)) a) (λ (a : ¬re = w_re), decidable.is_false _))))

theorem zsqrtd.ext {d : ℤ} {z w : ℤ√d} :

z = w ↔ z.re = w.re ∧ z.im = w.im

def zsqrtd.of_int {d : ℤ} :

ℤ → ℤ√d

Convert an integer to a ℤ√d

Equations

zsqrtd.of_int n = {re := n, im := 0}

theorem zsqrtd.of_int_re {d : ℤ} (n : ℤ) :

(zsqrtd.of_int n).re = n

theorem zsqrtd.of_int_im {d : ℤ} (n : ℤ) :

(zsqrtd.of_int n).im = 0

def zsqrtd.zero {d : ℤ} :

The zero of the ring

Equations

zsqrtd.zero = zsqrtd.of_int 0

@[instance]

def zsqrtd.has_zero {d : ℤ} :

has_zero (ℤ√d)

Equations

zsqrtd.has_zero = {zero := zsqrtd.zero d}

@[simp]

theorem zsqrtd.zero_re {d : ℤ} :

0.re = 0

@[simp]

theorem zsqrtd.zero_im {d : ℤ} :

0.im = 0

@[instance]

def zsqrtd.inhabited {d : ℤ} :

inhabited (ℤ√d)

Equations

zsqrtd.inhabited = {default := 0}

def zsqrtd.one {d : ℤ} :

The one of the ring

Equations

zsqrtd.one = zsqrtd.of_int 1

@[instance]

def zsqrtd.has_one {d : ℤ} :

has_one (ℤ√d)

Equations

zsqrtd.has_one = {one := zsqrtd.one d}

@[simp]

theorem zsqrtd.one_re {d : ℤ} :

1.re = 1

@[simp]

theorem zsqrtd.one_im {d : ℤ} :

1.im = 0

def zsqrtd.sqrtd {d : ℤ} :

The representative of √d in the ring

Equations

zsqrtd.sqrtd = {re := 0, im := 1}

@[simp]

theorem zsqrtd.sqrtd_re {d : ℤ} :

zsqrtd.sqrtd.re = 0

@[simp]

theorem zsqrtd.sqrtd_im {d : ℤ} :

zsqrtd.sqrtd.im = 1

def zsqrtd.add {d : ℤ} :

ℤ√d → ℤ√d → ℤ√d

Addition of elements of ℤ√d

Equations

{re := x, im := y}.add {re := x', im := y'} = {re := x + x', im := y + y'}

@[instance]

def zsqrtd.has_add {d : ℤ} :

has_add (ℤ√d)

Equations

zsqrtd.has_add = {add := zsqrtd.add d}

@[simp]

theorem zsqrtd.add_def {d : ℤ} (x y x' y' : ℤ) :

{re := x, im := y} + {re := x', im := y'} = {re := x + x', im := y + y'}

@[simp]

theorem zsqrtd.add_re {d : ℤ} (z w : ℤ√d) :

(z + w).re = z.re + w.re

@[simp]

theorem zsqrtd.add_im {d : ℤ} (z w : ℤ√d) :

(z + w).im = z.im + w.im

@[simp]

theorem zsqrtd.bit0_re {d : ℤ} (z : ℤ√d) :

(bit0 z).re = bit0 z.re

@[simp]

theorem zsqrtd.bit0_im {d : ℤ} (z : ℤ√d) :

(bit0 z).im = bit0 z.im

@[simp]

theorem zsqrtd.bit1_re {d : ℤ} (z : ℤ√d) :

(bit1 z).re = bit1 z.re

@[simp]

theorem zsqrtd.bit1_im {d : ℤ} (z : ℤ√d) :

(bit1 z).im = bit0 z.im

def zsqrtd.neg {d : ℤ} :

ℤ√d → ℤ√d

Negation in ℤ√d

Equations

{re := x, im := y}.neg = {re := -x, im := -y}

@[instance]

def zsqrtd.has_neg {d : ℤ} :

has_neg (ℤ√d)

Equations

zsqrtd.has_neg = {neg := zsqrtd.neg d}

@[simp]

theorem zsqrtd.neg_re {d : ℤ} (z : ℤ√d) :

(-z).re = -z.re

@[simp]

theorem zsqrtd.neg_im {d : ℤ} (z : ℤ√d) :

(-z).im = -z.im

def zsqrtd.conj {d : ℤ} :

ℤ√d → ℤ√d

Conjugation in ℤ√d. The conjugate of a + b √d is a - b √d.

Equations

{re := x, im := y}.conj = {re := x, im := -y}

@[simp]

theorem zsqrtd.conj_re {d : ℤ} (z : ℤ√d) :

z.conj.re = z.re

@[simp]

theorem zsqrtd.conj_im {d : ℤ} (z : ℤ√d) :

z.conj.im = -z.im

def zsqrtd.mul {d : ℤ} :

ℤ√d → ℤ√d → ℤ√d

Multiplication in ℤ√d

Equations

{re := x, im := y}.mul {re := x', im := y'} = {re := x * x' + d * y * y', im := x * y' + y * x'}

@[instance]

def zsqrtd.has_mul {d : ℤ} :

has_mul (ℤ√d)

Equations

zsqrtd.has_mul = {mul := zsqrtd.mul d}

@[simp]

theorem zsqrtd.mul_re {d : ℤ} (z w : ℤ√d) :

(z * w).re = z.re * w.re + d * z.im * w.im

@[simp]

theorem zsqrtd.mul_im {d : ℤ} (z w : ℤ√d) :

(z * w).im = z.re * w.im + z.im * w.re

@[instance]

def zsqrtd.comm_ring {d : ℤ} :

comm_ring (ℤ√d)

Equations

zsqrtd.comm_ring = {add := has_add.add zsqrtd.has_add, add_assoc := _, zero := 0, zero_add := _, add_zero := _, neg := has_neg.neg zsqrtd.has_neg, add_left_neg := _, add_comm := _, mul := has_mul.mul zsqrtd.has_mul, mul_assoc := _, one := 1, one_mul := _, mul_one := _, left_distrib := _, right_distrib := _, mul_comm := _}

@[instance]

def zsqrtd.add_comm_monoid {d : ℤ} :

add_comm_monoid (ℤ√d)

Equations

zsqrtd.add_comm_monoid = add_comm_group.to_add_comm_monoid (ℤ√d)

@[instance]

def zsqrtd.add_monoid {d : ℤ} :

add_monoid (ℤ√d)

Equations

zsqrtd.add_monoid = add_group.to_add_monoid (ℤ√d)

@[instance]

def zsqrtd.monoid {d : ℤ} :

monoid (ℤ√d)

Equations

zsqrtd.monoid = ring.to_monoid (ℤ√d)

@[instance]

def zsqrtd.comm_monoid {d : ℤ} :

comm_monoid (ℤ√d)

Equations

zsqrtd.comm_monoid = comm_semiring.to_comm_monoid (ℤ√d)

@[instance]

def zsqrtd.comm_semigroup {d : ℤ} :

comm_semigroup (ℤ√d)

Equations

zsqrtd.comm_semigroup = comm_ring.to_comm_semigroup (ℤ√d)

@[instance]

def zsqrtd.semigroup {d : ℤ} :

semigroup (ℤ√d)

Equations

zsqrtd.semigroup = monoid.to_semigroup (ℤ√d)

@[instance]

def zsqrtd.add_comm_semigroup {d : ℤ} :

add_comm_semigroup (ℤ√d)

Equations

zsqrtd.add_comm_semigroup = add_comm_monoid.to_add_comm_semigroup (ℤ√d)

@[instance]

def zsqrtd.add_semigroup {d : ℤ} :

add_semigroup (ℤ√d)

Equations

zsqrtd.add_semigroup = add_monoid.to_add_semigroup (ℤ√d)

@[instance]

def zsqrtd.comm_semiring {d : ℤ} :

comm_semiring (ℤ√d)

Equations

zsqrtd.comm_semiring = comm_ring.to_comm_semiring

@[instance]

def zsqrtd.semiring {d : ℤ} :

semiring (ℤ√d)

Equations

zsqrtd.semiring = ring.to_semiring

@[instance]

def zsqrtd.ring {d : ℤ} :

Equations

zsqrtd.ring = comm_ring.to_ring (ℤ√d)

@[instance]

def zsqrtd.distrib {d : ℤ} :

distrib (ℤ√d)

Equations

zsqrtd.distrib = ring.to_distrib (ℤ√d)

@[instance]

def zsqrtd.nontrivial {d : ℤ} :

nontrivial (ℤ√d)

Equations

zsqrtd.nontrivial = _

@[simp]

theorem zsqrtd.coe_nat_re {d : ℤ} (n : ℕ) :

@[simp]

theorem zsqrtd.coe_nat_im {d : ℤ} (n : ℕ) :

theorem zsqrtd.coe_nat_val {d : ℤ} (n : ℕ) :

↑n = {re := ↑n, im := 0}

@[simp]

theorem zsqrtd.coe_int_re {d : ℤ} (n : ℤ) :

@[simp]

theorem zsqrtd.coe_int_im {d : ℤ} (n : ℤ) :

theorem zsqrtd.coe_int_val {d : ℤ} (n : ℤ) :

↑n = {re := n, im := 0}

@[instance]

def zsqrtd.char_zero {d : ℤ} :

char_zero (ℤ√d)

Equations

zsqrtd.char_zero = _

@[simp]

theorem zsqrtd.of_int_eq_coe {d : ℤ} (n : ℤ) :

zsqrtd.of_int n = ↑n

@[simp]

theorem zsqrtd.smul_val {d : ℤ} (n x y : ℤ) :

↑n * {re := x, im := y} = {re := n * x, im := n * y}

@[simp]

theorem zsqrtd.muld_val {d : ℤ} (x y : ℤ) :

zsqrtd.sqrtd * {re := x, im := y} = {re := d * y, im := x}

@[simp]

theorem zsqrtd.smuld_val {d : ℤ} (n x y : ℤ) :

zsqrtd.sqrtd * ↑n * {re := x, im := y} = {re := d * n * y, im := n * x}

theorem zsqrtd.decompose {d x y : ℤ} :

{re := x, im := y} = ↑x + zsqrtd.sqrtd * ↑y

theorem zsqrtd.mul_conj {d x y : ℤ} :

{re := x, im := y} * {re := x, im := y}.conj = ↑x * ↑x - ↑d * ↑y * ↑y

theorem zsqrtd.conj_mul {d : ℤ} {a b : ℤ√d} :

(a * b).conj = a.conj * b.conj

theorem zsqrtd.coe_int_add {d : ℤ} (m n : ℤ) :

↑(m + n) = ↑m + ↑n

theorem zsqrtd.coe_int_sub {d : ℤ} (m n : ℤ) :

↑(m - n) = ↑m - ↑n

theorem zsqrtd.coe_int_mul {d : ℤ} (m n : ℤ) :

↑(m * n) = ↑m * ↑n

theorem zsqrtd.coe_int_inj {d m n : ℤ} :

↑m = ↑n → m = n

def zsqrtd.sq_le :

ℕ → ℕ → ℕ → ℕ → Prop

Read sq_le a c b d as a √c ≤ b √d

Equations

zsqrtd.sq_le a c b d = (c * a * a ≤ d * b * b)

theorem zsqrtd.sq_le_of_le {c d x y z w : ℕ} :

z ≤ x → y ≤ w → zsqrtd.sq_le x c y d → zsqrtd.sq_le z c w d

theorem zsqrtd.sq_le_add_mixed {c d x y z w : ℕ} :

zsqrtd.sq_le x c y d → zsqrtd.sq_le z c w d → c * (x * z) ≤ d * (y * w)

theorem zsqrtd.sq_le_add {c d x y z w : ℕ} :

zsqrtd.sq_le x c y d → zsqrtd.sq_le z c w d → zsqrtd.sq_le (x + z) c (y + w) d

theorem zsqrtd.sq_le_cancel {c d x y z w : ℕ} :

zsqrtd.sq_le y d x c → zsqrtd.sq_le (x + z) c (y + w) d → zsqrtd.sq_le z c w d

theorem zsqrtd.sq_le_smul {c d x y : ℕ} (n : ℕ) :

zsqrtd.sq_le x c y d → zsqrtd.sq_le (n * x) c (n * y) d

theorem zsqrtd.sq_le_mul {d x y z w : ℕ} :

(zsqrtd.sq_le x 1 y d → zsqrtd.sq_le z 1 w d → zsqrtd.sq_le (x * w + y * z) d (x * z + d * y * w) 1) ∧ (zsqrtd.sq_le x 1 y d → zsqrtd.sq_le w d z 1 → zsqrtd.sq_le (x * z + d * y * w) 1 (x * w + y * z) d) ∧ (zsqrtd.sq_le y d x 1 → zsqrtd.sq_le z 1 w d → zsqrtd.sq_le (x * z + d * y * w) 1 (x * w + y * z) d) ∧ (zsqrtd.sq_le y d x 1 → zsqrtd.sq_le w d z 1 → zsqrtd.sq_le (x * w + y * z) d (x * z + d * y * w) 1)

def zsqrtd.nonnegg :

ℕ → ℕ → ℤ → ℤ → Prop

"Generalized" nonneg. nonnegg c d x y means a √c + b √d ≥ 0; we are interested in the case c = 1 but this is more symmetric

Equations

zsqrtd.nonnegg c d -[1+ a] -[1+ b] = false
zsqrtd.nonnegg c d -[1+ a] ↑b = zsqrtd.sq_le (a + 1) d b c
zsqrtd.nonnegg c d ↑a -[1+ b] = zsqrtd.sq_le (b + 1) c a d
zsqrtd.nonnegg c d ↑a ↑b = true

theorem zsqrtd.nonnegg_comm {c d : ℕ} {x y : ℤ} :

zsqrtd.nonnegg c d x y = zsqrtd.nonnegg d c y x

theorem zsqrtd.nonnegg_neg_pos {c d a b : ℕ} :

zsqrtd.nonnegg c d (-↑a) ↑b ↔ zsqrtd.sq_le a d b c

theorem zsqrtd.nonnegg_pos_neg {c d a b : ℕ} :

zsqrtd.nonnegg c d ↑a (-↑b) ↔ zsqrtd.sq_le b c a d

theorem zsqrtd.nonnegg_cases_right {c d a : ℕ} {b : ℤ} :

(∀ (x : ℕ), b = -↑x → zsqrtd.sq_le x c a d) → zsqrtd.nonnegg c d ↑a b

theorem zsqrtd.nonnegg_cases_left {c d b : ℕ} {a : ℤ} :

(∀ (x : ℕ), a = -↑x → zsqrtd.sq_le x d b c) → zsqrtd.nonnegg c d a ↑b

def zsqrtd.norm {d : ℤ} :

ℤ√d → ℤ

Equations

n.norm = n.re * n.re - d * n.im * n.im

@[simp]

theorem zsqrtd.norm_zero {d : ℤ} :

0.norm = 0

@[simp]

theorem zsqrtd.norm_one {d : ℤ} :

1.norm = 1

@[simp]

theorem zsqrtd.norm_int_cast {d : ℤ} (n : ℤ) :

↑n.norm = n * n

@[simp]

theorem zsqrtd.norm_nat_cast {d : ℤ} (n : ℕ) :

↑n.norm = ↑n * ↑n

@[simp]

theorem zsqrtd.norm_mul {d : ℤ} (n m : ℤ√d) :

(n * m).norm = n.norm * m.norm

theorem zsqrtd.norm_eq_mul_conj {d : ℤ} (n : ℤ√d) :

↑(n.norm) = n * n.conj

@[instance]

def zsqrtd.is_monoid_hom {d : ℤ} :

is_monoid_hom zsqrtd.norm

Equations

zsqrtd.is_monoid_hom = _

theorem zsqrtd.norm_nonneg {d : ℤ} (hd : d ≤ 0) (n : ℤ√d) :

theorem zsqrtd.norm_eq_one_iff {d : ℤ} {x : ℤ√d} :

x.norm.nat_abs = 1 ↔ is_unit x

def zsqrtd.nonneg {d : ℕ} :

ℤ√↑d → Prop

Nonnegativity of an element of ℤ√d.

Equations

{re := a, im := b}.nonneg = zsqrtd.nonnegg d 1 a b

def zsqrtd.le {d : ℕ} :

ℤ√↑d → ℤ√↑d → Prop

Equations

a.le b = (b - a).nonneg

@[instance]

def zsqrtd.has_le {d : ℕ} :

has_le (ℤ√↑d)

Equations

zsqrtd.has_le = {le := zsqrtd.le d}

def zsqrtd.lt {d : ℕ} :

ℤ√↑d → ℤ√↑d → Prop

Equations

a.lt b = ¬b ≤ a

@[instance]

def zsqrtd.has_lt {d : ℕ} :

has_lt (ℤ√↑d)

Equations

zsqrtd.has_lt = {lt := zsqrtd.lt d}

@[instance]

def zsqrtd.decidable_nonnegg (c d : ℕ) (a b : ℤ) :

decidable (zsqrtd.nonnegg c d a b)

Equations

zsqrtd.decidable_nonnegg c d a b = a.cases_on (λ (a : ℕ), b.cases_on (λ (b : ℕ), _.mpr (_.mpr (_.mpr decidable.true))) (λ (b : ℕ), _.mpr (_.mpr ((c * (b + 1) * (b + 1)).decidable_le (d * a * a))))) (λ (a : ℕ), b.cases_on (λ (b : ℕ), _.mpr (_.mpr ((d * (a + 1) * (a + 1)).decidable_le (c * b * b)))) (λ (b : ℕ), _.mpr decidable.false))

@[instance]

def zsqrtd.decidable_nonneg {d : ℕ} (a : ℤ√↑d) :

decidable a.nonneg

Equations

{re := a, im := b}.decidable_nonneg = zsqrtd.decidable_nonnegg d 1 a b

@[instance]

def zsqrtd.decidable_le {d : ℕ} (a b : ℤ√↑d) :

decidable (a ≤ b)

Equations

a.decidable_le b = (b - a).decidable_nonneg

theorem zsqrtd.nonneg_cases {d : ℕ} {a : ℤ√↑d} :

a.nonneg → (∃ (x y : ℕ), a = {re := ↑x, im := ↑y} ∨ a = {re := ↑x, im := -↑y} ∨ a = {re := -↑x, im := ↑y})

theorem zsqrtd.nonneg_add_lem {d x y z w : ℕ} :

{re := ↑x, im := -↑y}.nonneg → {re := -↑z, im := ↑w}.nonneg → ({re := ↑x, im := -↑y} + {re := -↑z, im := ↑w}).nonneg

theorem zsqrtd.nonneg_add {d : ℕ} {a b : ℤ√↑d} :

a.nonneg → b.nonneg → (a + b).nonneg

theorem zsqrtd.le_refl {d : ℕ} (a : ℤ√↑d) :

a ≤ a

theorem zsqrtd.le_trans {d : ℕ} {a b c : ℤ√↑d} :

a ≤ b → b ≤ c → a ≤ c

theorem zsqrtd.nonneg_iff_zero_le {d : ℕ} {a : ℤ√↑d} :

a.nonneg ↔ 0 ≤ a

theorem zsqrtd.le_of_le_le {d : ℕ} {x y z w : ℤ} :

x ≤ z → y ≤ w → {re := x, im := y} ≤ {re := z, im := w}

theorem zsqrtd.le_arch {d : ℕ} (a : ℤ√↑d) :

∃ (n : ℕ), a ≤ ↑n

theorem zsqrtd.nonneg_total {d : ℕ} (a : ℤ√↑d) :

a.nonneg ∨ (-a).nonneg

theorem zsqrtd.le_total {d : ℕ} (a b : ℤ√↑d) :

a ≤ b ∨ b ≤ a

@[instance]

def zsqrtd.preorder {d : ℕ} :

preorder (ℤ√↑d)

Equations

zsqrtd.preorder = {le := zsqrtd.le d, lt := zsqrtd.lt d, le_refl := _, le_trans := _, lt_iff_le_not_le := _}

theorem zsqrtd.add_le_add_left {d : ℕ} (a b : ℤ√↑d) (ab : a ≤ b) (c : ℤ√↑d) :

c + a ≤ c + b

theorem zsqrtd.le_of_add_le_add_left {d : ℕ} (a b c : ℤ√↑d) :

c + a ≤ c + b → a ≤ b

theorem zsqrtd.add_lt_add_left {d : ℕ} (a b : ℤ√↑d) (h : a < b) (c : ℤ√↑d) :

c + a < c + b

theorem zsqrtd.nonneg_smul {d : ℕ} {a : ℤ√↑d} {n : ℕ} :

a.nonneg → (↑n * a).nonneg

theorem zsqrtd.nonneg_muld {d : ℕ} {a : ℤ√↑d} :

a.nonneg → (zsqrtd.sqrtd * a).nonneg

theorem zsqrtd.nonneg_mul_lem {d x y : ℕ} {a : ℤ√↑d} :

a.nonneg → ({re := ↑x, im := ↑y} * a).nonneg

theorem zsqrtd.nonneg_mul {d : ℕ} {a b : ℤ√↑d} :

a.nonneg → b.nonneg → (a * b).nonneg

theorem zsqrtd.mul_nonneg {d : ℕ} (a b : ℤ√↑d) :

0 ≤ a → 0 ≤ b → 0 ≤ a * b

theorem zsqrtd.not_sq_le_succ (c d y : ℕ) :

0 < c → ¬zsqrtd.sq_le (y + 1) c 0 d

@[class]

structure zsqrtd.nonsquare :

ℕ → Prop

ns : ∀ (n : ℕ), x ≠ n * n

A nonsquare is a natural number that is not equal to the square of an integer. This is implemented as a typeclass because it's a necessary condition for much of the Pell equation theory.

Instances

pell.dnsq

theorem zsqrtd.d_pos {d : ℕ} [dnsq : zsqrtd.nonsquare d] :

0 < d

theorem zsqrtd.divides_sq_eq_zero {d : ℕ} [dnsq : zsqrtd.nonsquare d] {x y : ℕ} :

x * x = d * y * y → x = 0 ∧ y = 0

theorem zsqrtd.divides_sq_eq_zero_z {d : ℕ} [dnsq : zsqrtd.nonsquare d] {x y : ℤ} :

x * x = ↑d * y * y → x = 0 ∧ y = 0

theorem zsqrtd.not_divides_square {d : ℕ} [dnsq : zsqrtd.nonsquare d] (x y : ℕ) :

(x + 1) * (x + 1) ≠ d * (y + 1) * (y + 1)

theorem zsqrtd.nonneg_antisymm {d : ℕ} [dnsq : zsqrtd.nonsquare d] {a : ℤ√↑d} :

a.nonneg → (-a).nonneg → a = 0

theorem zsqrtd.le_antisymm {d : ℕ} [dnsq : zsqrtd.nonsquare d] {a b : ℤ√↑d} :

a ≤ b → b ≤ a → a = b

@[instance]

def zsqrtd.decidable_linear_order {d : ℕ} [dnsq : zsqrtd.nonsquare d] :

decidable_linear_order (ℤ√↑d)

Equations

zsqrtd.decidable_linear_order = {le := preorder.le zsqrtd.preorder, lt := preorder.lt zsqrtd.preorder, le_refl := _, le_trans := _, lt_iff_le_not_le := _, le_antisymm := _, le_total := _, decidable_le := zsqrtd.decidable_le d, decidable_eq := decidable_eq_of_decidable_le zsqrtd.decidable_le, decidable_lt := decidable_lt_of_decidable_le zsqrtd.decidable_le}

theorem zsqrtd.eq_zero_or_eq_zero_of_mul_eq_zero {d : ℕ} [dnsq : zsqrtd.nonsquare d] {a b : ℤ√↑d} :

a * b = 0 → a = 0 ∨ b = 0

@[instance]

def zsqrtd.integral_domain {d : ℕ} [dnsq : zsqrtd.nonsquare d] :

integral_domain (ℤ√↑d)

Equations

zsqrtd.integral_domain = {add := comm_ring.add zsqrtd.comm_ring, add_assoc := _, zero := comm_ring.zero zsqrtd.comm_ring, zero_add := _, add_zero := _, neg := comm_ring.neg zsqrtd.comm_ring, add_left_neg := _, add_comm := _, mul := comm_ring.mul zsqrtd.comm_ring, mul_assoc := _, one := comm_ring.one zsqrtd.comm_ring, one_mul := _, mul_one := _, left_distrib := _, right_distrib := _, mul_comm := _, exists_pair_ne := _, eq_zero_or_eq_zero_of_mul_eq_zero := _}

theorem zsqrtd.mul_pos {d : ℕ} [dnsq : zsqrtd.nonsquare d] (a b : ℤ√↑d) :

0 < a → 0 < b → 0 < a * b

@[instance]

def zsqrtd.decidable_linear_ordered_comm_ring {d : ℕ} [dnsq : zsqrtd.nonsquare d] :

decidable_linear_ordered_comm_ring (ℤ√↑d)

Equations

zsqrtd.decidable_linear_ordered_comm_ring = {add := comm_ring.add zsqrtd.comm_ring, add_assoc := _, zero := comm_ring.zero zsqrtd.comm_ring, zero_add := _, add_zero := _, neg := comm_ring.neg zsqrtd.comm_ring, add_left_neg := _, add_comm := _, mul := comm_ring.mul zsqrtd.comm_ring, mul_assoc := _, one := comm_ring.one zsqrtd.comm_ring, one_mul := _, mul_one := _, left_distrib := _, right_distrib := _, le := decidable_linear_order.le zsqrtd.decidable_linear_order, lt := decidable_linear_order.lt zsqrtd.decidable_linear_order, le_refl := _, le_trans := _, lt_iff_le_not_le := _, le_antisymm := _, add_le_add_left := _, exists_pair_ne := _, mul_pos := _, le_total := _, zero_lt_one := _, mul_comm := _, decidable_le := decidable_linear_order.decidable_le zsqrtd.decidable_linear_order, decidable_eq := decidable_linear_order.decidable_eq zsqrtd.decidable_linear_order, decidable_lt := decidable_linear_order.decidable_lt zsqrtd.decidable_linear_order}

@[instance]

def zsqrtd.decidable_linear_ordered_semiring {d : ℕ} [dnsq : zsqrtd.nonsquare d] :

decidable_linear_ordered_semiring (ℤ√↑d)

Equations

zsqrtd.decidable_linear_ordered_semiring = decidable_linear_ordered_comm_ring.to_decidable_linear_ordered_semiring

@[instance]

def zsqrtd.linear_ordered_semiring {d : ℕ} [dnsq : zsqrtd.nonsquare d] :

linear_ordered_semiring (ℤ√↑d)

Equations

zsqrtd.linear_ordered_semiring = linear_ordered_ring.to_linear_ordered_semiring

@[instance]

def zsqrtd.ordered_semiring {d : ℕ} [dnsq : zsqrtd.nonsquare d] :

ordered_semiring (ℤ√↑d)

Equations

zsqrtd.ordered_semiring = ordered_ring.to_ordered_semiring

General documentation

Additional documentation

mathlib overview

well founded recursion

documentation style guide

naming conventions

Library

algebra

big_operators

basic

intervals

order

pi

ring

category

Algebra

basic

limits

CommRing

adjunctions

basic

colimits

limits

Group

Z_Module_equivalence

abelian

adjunctions

basic

biproducts

colimits

images

limits

preadditive

zero

Module

abelian

basic

kernels

limits

monoidal

Mon

basic

colimits

limits

continued_fractions

computation

approximations

basic

correctness_terminating

translations

basic

continuants_recurrence

convergents_equiv

terminated_stable

translations

group

basic

commute

conj

defs

hom

inj_surj

pi

prod

semiconj

to_additive

type_tags

ulift

units

units_hom

with_one

homology

chain_complex

exact

homology

image_to_kernel_map

module

basic

ordered

pi

prod

submodule

ulift

polynomial

big_operators

ring

basic

pi

prod

ulift

add_torsor

archimedean

associated

char_p

char_zero

classical_lie_algebras

direct_limit

direct_sum

divisibility

euclidean_domain

field

field_power

floor

free

free_monoid

gcd_monoid

geom_sum

group_action_hom

group_power

group_ring_action

group_with_zero

group_with_zero_power

invertible

iterate_hom

lie_algebra

linear_ordered_comm_group_with_zero

linear_recurrence

midpoint

opposites

order

order_functions

ordered_field

ordered_group

ordered_ring

pointwise

punit_instances

quadratic_discriminant

algebraic_geometry

presheafed_space

prime_spectrum

stalks

analysis

ODE

gronwall

analytic

basic

composition

calculus

darboux

deriv

extend_deriv

fderiv

implicit

inverse

iterated_deriv

lhopital

local_extr

mean_value

specific_functions

tangent_cone

times_cont_diff

complex

basic

polynomial

convex

basic

caratheodory

cone

extrema

specific_functions

topology

normed_space

add_torsor

banach

basic

bounded_linear_maps

complemented

dual

enorm

extend

finite_dimension

hahn_banach

indicator_function

mazur_ulam

multilinear

operator_norm

point_reflection

real_inner_product

riesz_lemma

units

special_functions

arsinh

exp_log

pow

trigonometric

asymptotics

hofer

mean_inequalities

specific_limits

category_theory

abelian

diagram_lemmas

four

basic

exact

non_preadditive

pseudoelements

adjunction

basic

fully_faithful

limits

opposites

category

Cat

Groupoid

Kleisli

Rel

default

closed

cartesian

monoidal

concrete_category

basic

bundled

bundled_hom

reflects_isomorphisms

unbundled_hom

limits

preserves

basic

shapes

shapes

constructions

over

connected

default

products

binary_products

equalizers

limits_of_products_and_equalizers

preserve_binary_products

pullbacks

binary_products

biproducts

concrete_category

equalizers

finite_limits

finite_products

images

kernels

products

pullbacks

regular_mono

strong_epi

terminal

types

wide_pullbacks

zero

concrete_category

cones

connected

creates

fubini

functor_category

lattice

limits

opposites

over

pi

punit

types

monad

adjunction

algebra

basic

bundled

equiv_mon

limits

types

monoidal

internal

functor_category

types

End

braided

category

functor

functor_category

functorial

internal

of_has_finite_products

types

unitors

pi

basic

preadditive

biproducts

default

schur

products

associator

basic

bifunctor

sums

associator

basic

action

arrow

comma

conj

connected

const

core

currying

differential_object

discrete_category

elements

endomorphism

epi_mono

eq_to_hom

equivalence

full_subcategory

fully_faithful

functor

functor_category

functorial

graded_object

groupoid

hom_functor

isomorphism

isomorphism_classes

natural_isomorphism

natural_transformation

opposites

over

pempty

punit

quotient

reflects_isomorphisms

shift

simple

single_obj

sparse

types

whiskering

yoneda

combinatorics

composition

simple_graph

computability

halting

partrec

partrec_code

primrec

reduce

tm_to_partrec

turing_machine

control

bitraversable

basic

instances

lemmas

equiv_functor

instances

functor

multivariate

monad

basic

cont

writer

traversable

basic

derive

equiv

instances

lemmas

applicative

basic

bifunctor

equiv_functor

fold

functor

uliftable

core

data

buffer

parser

bitvec

buffer

dlist

lazy_list

stream

vector

init

algebra

classes

functions

order

control

alternative

applicative

combinators

except

functor

id

lawful

lift

monad

monad_fail

option

reader

state

data

array

basic

slice

bool

basic

lemmas

char

basic

classes

lemmas

fin

basic

ops

int

basic

bitwise

comp_lemmas

order

list

basic

instances

lemmas

qsort

nat

basic

bitwise

div

gcd

lemmas

option

basic

instances

ordering

basic

lemmas

rbmap

basic

rbtree

basic

default

sigma

basic

lex

string

basic

ops

subtype

basic

instances

sum

basic

unsigned

basic

ops

prod

punit

quot

repr

set

setoid

to_string

meta

converter

conv

interactive

lean

parser

smt

congruence_closure

ematch

interactive

rsimp

smt_tactic

widget

basic

html_cmd

interactive_expr

replace_save_info

tactic_component

ac_tactics

async_tactic

attribute

backward

case_tag

comp_value_tactics

congr_lemma

congr_tactic

constructor_tactic

contradiction_tactic

declaration

derive

environment

exceptional

expr

expr_address

float

format

fun_info

has_reflect

hole_command

injection_tactic

interaction_monad

interactive

interactive_base

level

local_context

match_tactic

mk_dec_eq_instance

mk_has_reflect_instance

mk_has_sizeof_instance

mk_inhabited_instance

module_info

name

occurrences

options

pexpr

rb_map

rec_util

ref

relation_tactics

rewrite_tactic

set_get_option_tactics

simp_tactic

tactic

tagged_format

task

type_context

vm

well_founded_tactics

cc_lemmas

classical

coe

core

default

function

funext

ite_simp

logic

propext

util

version

wf

system

io

io_interface

random

data

analysis

filter

topology

array

lemmas

bitvec

basic

buffer

basic

complex

basic

exponential

module

dlist

basic

instances

equiv

encodable

basic

lattice

basic

denumerable

fin

functor

list

local_equiv

mul_add

nat

ring

transfer_instance

finset

basic

fold

intervals

lattice

nat_antidiagonal

order

pi

powerset

sort

finsupp

basic

lattice

pointwise

fintype

basic

card

intervals

sort

fp

basic

int

basic

cast

char_zero

gcd

modeq

parity

range

sqrt

list

alist

bag_inter

basic

chain

defs

erase_dup

forall2

func

indexes

intervals

min_max

nat_antidiagonal

nodup

of_fn

pairwise

palindrome

perm

range

rotate

sections

sigma

sort

tfae

zip

matrix

basic

notation

pequiv

multiset

antidiagonal

basic

erase_dup

finset_ops

fold

functor

intervals

lattice

nat_antidiagonal

nodup

pi

powerset

range

sections

sort

nat

basic

cast

choose

digits

dist

enat

fib

gcd

modeq

multiplicity

pairing

parity

prime

sqrt

totient

num

basic

bitwise

lemmas

prime

option

basic

defs

padics

hensel

padic_integers

padic_norm

padic_numbers

pfunctor

multivariate

M

W

basic

univariate

M

basic

pnat

basic

factors

intervals

xgcd

polynomial

degree

basic

algebra_map

basic

coeff

degree

derivative

div

eval

field_division

identities

induction

integral_normalization

monic

monomial

ring_division

qpf

multivariate

constructions

cofix

comp

const

fix

prj

quot

sigma

basic

univariate

basic

rat

basic

cast

denumerable

floor

meta_defs

order

sqrt

real

basic

cardinality

cau_seq

cau_seq_completion

conjugate_exponents

ennreal

ereal

golden_ratio

hyperreal

irrational

nnreal

pi

seq

computation

parallel

seq

wseq

set

intervals

basic

disjoint

image_preimage

ord_connected

unordered_interval

basic

countable

disjointed

enumerate

finite

function

lattice

setoid

basic

partition

sigma

basic

stream

basic

string

basic

defs

zmod

basic

zsqrtd

basic

gaussian_int

W

bool

char

dfinsupp

erased

fin

fin2

fin_enum

finmap

hash_map

holor

indicator_function

lazy_list2

mllist

monoid_algebra

mv_polynomial

opposite

pequiv

pfun

prod

quot

rel

semiquot

subtype

sum

support

sym

sym2

tree

typevec

ulift

vector2

deprecated

group

ring

subgroup

submonoid

dynamics

circle

rotation_number

translation_number

fixed_points

basic

topology

periodic_pts

field_theory

algebraic_closure

chevalley_warning

finite

fixed

minimal_polynomial

mv_polynomial

normal

perfect_closure

separable

splitting_field

subfield

tower

geometry

algebra

lie_group

euclidean

basic

circumcenter

monge_point

triangle

manifold

basic_smooth_bundle

charted_space

local_invariant_properties

mfderiv

real_instances

smooth_manifold_with_corners

times_cont_mdiff

group_theory

perm

cycles

sign

submonoid

basic

membership

operations

abelianization

congruence

coset

eckmann_hilton

free_abelian_group

free_group

group_action

monoid_localization

order_of_element

presented_group

quotient_group

semidirect_product

subgroup

sylow

linear_algebra

affine_space

basic

combination

finite_dimensional

independent

char_poly

coeff

direct_sum

finsupp

tensor_product

adic_completion

basic

basis

bilinear_form

char_poly

contraction

determinant

dimension

direct_sum_module

dual

finite_dimensional

finsupp

finsupp_vector_space

invariant_basis_number

lagrange

linear_action

linear_pmap

matrix

multilinear

nonsingular_inverse

projection

quadratic_form

sesquilinear_form

smodeq

special_linear_group

tensor_algebra

tensor_product

logic

function

basic

conjugate

iterate

basic

embedding

nontrivial

relation

relator

unique

measure_theory

category

Meas

ae_eq_fun

bochner_integration

borel_space

content

decomposition

giry_monad

group

haar_measure

integration

interval_integral

l1_space

lebesgue_measure

measurable_space

measure_space

outer_measure

probability_mass_function

set_integral

simple_func_dense

meta

coinductive_predicates

expr

expr_lens

rb_map

uchange

number_theory

basic

bernoulli

dioph

lucas_lehmer

pell

primorial

pythagorean_triples

quadratic_reciprocity

sum_four_squares

sum_two_squares

order

category

LinearOrder

NonemptyFinLinOrd

PartialOrder

Preorder

filter

at_top_bot

bases

basic

cofinite

countable_Inter

extr

filter_product

germ

indicator_function

interval

lift

partial

pointwise

ultrafilter

basic

boolean_algebra

bounded_lattice

bounds

complete_boolean_algebra

complete_lattice

conditionally_complete_lattice

copy

directed

fixed_points

galois_connection

ideal

iterate

lattice

lexicographic

liminf_limsup

ord_continuous

order_iso_nat

pilex

rel_classes

rel_iso

semiconj_Sup

zorn

representation_theory

maschke

ring_theory

ideal

basic

operations

over

polynomial

basic

homogeneous

rational_root

valuation

basic

adjoin

adjoin_root

algebra

algebra_operations

algebra_tower

algebraic

coprime

derivation

discrete_valuation_ring

eisenstein_criterion

euclidean_domain

fintype

fractional_ideal

free_comm_ring

free_ring

integral_closure

integral_domain

jacobson

jacobson_ideal

localization

maps

matrix_algebra

multiplicity

noetherian

polynomial_algebra

power_series

prime

principal_ideal_domain

subring

subsemiring

tensor_product

unique_factorization_domain

set_theory

game

domineering

impartial

nim

short

state

winner

cardinal

cardinal_ordinal

cofinality

game

lists

ordinal

ordinal_arithmetic

ordinal_notation

pgame

schroeder_bernstein

surreal

zfc

system

random

basic

tactic

converter

apply_congr

binders

interactive

old_conv

linarith

datatypes

elimination

frontend

lemmas

parsing

preprocessing

verification

lint

basic

default

frontend

misc

simp

type_classes

monotonicity

basic

interactive

lemmas

nth_rewrite

basic

congr

default

omega

int

dnf

form

main

preterm

nat

dnf

form

main

neg_elim

preterm

sub_elim

clause

coeffs

eq_elim

find_ees

find_scalars

lin_comb

main

misc

prove_unsats

term

rewrite_all

basic

abel

algebra

alias

apply

apply_fun

auto_cases

binder_matching

cache

cancel_denoms

chain

choose

clear

core

dec_trivial

delta_instance

derive_fintype

derive_inhabited

doc_commands

elide

equiv_rw

explode

ext

fin_cases

find

find_unused

finish

fix_reflect_string

generalize_proofs

generalizes

group

hint

interactive

interactive_expr

interval_cases

lift

local_cache

localized

mk_iff_of_inductive_prop

noncomm_ring

norm_cast

norm_num

obviously

pi_instances

protected

push_neg

rcases

reassoc_axiom

rename_var

replacer

restate_axiom

rewrite

ring

ring2

ring_exp

scc

show_term

simp_command

simp_result

simp_rw

simpa

simps

slice

solve_by_elim

split_ifs

squeeze

subtype_instance

suggest

tauto

tfae

tidy

transfer

transform_decl

transport

trunc_cases

unfold_cases

where

with_local_reducibility

wlog

zify

topology

algebra

affine

continuous_functions

group

group_completion

infinite_sum

module

monoid

multilinear

open_subgroup

ordered

polynomial

ring

uniform_group

uniform_ring

category

Top

adjunctions

basic

epi_mono

limits

open_nhds

opens

TopCommRing

UniformSpace

instances

complex

ennreal

nnreal

real

real_vector_space

metric_space

antilipschitz

baire

basic

cau_seq_filter

closeds

completion

contracting

emetric_space

gluing

gromov_hausdorff

gromov_hausdorff_realized

hausdorff_distance

isometry

lipschitz

pi_Lp

premetric_space

sheaves

presheaf

presheaf_of_functions

sheaf

sheaf_of_functions

stalks

uniform_space

absolute_value

abstract_completion

basic

cauchy

compact_separated

compare_reals

complete_separated

completion

pi

separation

uniform_convergence

uniform_embedding

bases

basic

bounded_continuous_function

compact_open

compacts

constructions

continuous_map

continuous_on

dense_embedding

extend_from_subset

homeomorph

list

local_extr

local_homeomorph

maps

opens

order

path_connected

separation

sequences

stone_cech

subset_properties

tactic

topological_fiber_bundle