[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
s : Finset R
degree_f_lt : degree f < ↑(Finset.card s)
eval_f : ∀ (x : R), x ∈ s → eval x f = 0
⊢ f = 0
[PROOFSTEP]
rw [← mem_degreeLT] at degree_f_lt 
[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
s : Finset R
degree_f_lt : f ∈ degreeLT R (Finset.card s)
eval_f : ∀ (x : R), x ∈ s → eval x f = 0
⊢ f = 0
[PROOFSTEP]
simp_rw [eval_eq_sum_degreeLTEquiv degree_f_lt] at eval_f 
[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
s : Finset R
degree_f_lt : f ∈ degreeLT R (Finset.card s)
eval_f :
  ∀ (x : R),
    x ∈ s →
      ∑ x_1 : Fin (Finset.card s),
          ↑(degreeLTEquiv R (Finset.card s)) { val := f, property := degree_f_lt } x_1 * x ^ ↑x_1 =
        0
⊢ f = 0
[PROOFSTEP]
rw [← degreeLTEquiv_eq_zero_iff_eq_zero degree_f_lt]
[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
s : Finset R
degree_f_lt : f ∈ degreeLT R (Finset.card s)
eval_f :
  ∀ (x : R),
    x ∈ s →
      ∑ x_1 : Fin (Finset.card s),
          ↑(degreeLTEquiv R (Finset.card s)) { val := f, property := degree_f_lt } x_1 * x ^ ↑x_1 =
        0
⊢ ↑(degreeLTEquiv R (Finset.card s)) { val := f, property := degree_f_lt } = 0
[PROOFSTEP]
exact
  Matrix.eq_zero_of_forall_index_sum_mul_pow_eq_zero
    (Injective.comp (Embedding.subtype _).inj' (equivFinOfCardEq (card_coe _)).symm.injective) fun _ =>
    eval_f _ (Finset.coe_mem _)
[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
s : Finset R
degree_fg_lt : degree (f - g) < ↑(Finset.card s)
eval_fg : ∀ (x : R), x ∈ s → eval x f = eval x g
⊢ f = g
[PROOFSTEP]
rw [← sub_eq_zero]
[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
s : Finset R
degree_fg_lt : degree (f - g) < ↑(Finset.card s)
eval_fg : ∀ (x : R), x ∈ s → eval x f = eval x g
⊢ f - g = 0
[PROOFSTEP]
refine' eq_zero_of_degree_lt_of_eval_finset_eq_zero _ degree_fg_lt _
[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
s : Finset R
degree_fg_lt : degree (f - g) < ↑(Finset.card s)
eval_fg : ∀ (x : R), x ∈ s → eval x f = eval x g
⊢ ∀ (x : R), x ∈ s → eval x (f - g) = 0
[PROOFSTEP]
simp_rw [eval_sub, sub_eq_zero]
[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
s : Finset R
degree_fg_lt : degree (f - g) < ↑(Finset.card s)
eval_fg : ∀ (x : R), x ∈ s → eval x f = eval x g
⊢ ∀ (x : R), x ∈ s → eval x f = eval x g
[PROOFSTEP]
exact eval_fg
[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
s : Finset R
degree_f_lt : degree f < ↑(Finset.card s)
degree_g_lt : degree g < ↑(Finset.card s)
eval_fg : ∀ (x : R), x ∈ s → eval x f = eval x g
⊢ f = g
[PROOFSTEP]
rw [← mem_degreeLT] at degree_f_lt degree_g_lt 
[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
s : Finset R
degree_f_lt : f ∈ degreeLT R (Finset.card s)
degree_g_lt : g ∈ degreeLT R (Finset.card s)
eval_fg : ∀ (x : R), x ∈ s → eval x f = eval x g
⊢ f = g
[PROOFSTEP]
refine' eq_of_degree_sub_lt_of_eval_finset_eq _ _ eval_fg
[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
s : Finset R
degree_f_lt : f ∈ degreeLT R (Finset.card s)
degree_g_lt : g ∈ degreeLT R (Finset.card s)
eval_fg : ∀ (x : R), x ∈ s → eval x f = eval x g
⊢ degree (f - g) < ↑(Finset.card s)
[PROOFSTEP]
rw [← mem_degreeLT]
[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
s : Finset R
degree_f_lt : f ∈ degreeLT R (Finset.card s)
degree_g_lt : g ∈ degreeLT R (Finset.card s)
eval_fg : ∀ (x : R), x ∈ s → eval x f = eval x g
⊢ f - g ∈ degreeLT R (Finset.card s)
[PROOFSTEP]
exact Submodule.sub_mem _ degree_f_lt degree_g_lt
[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
s : Finset R
h_deg_le : degree f ≤ ↑(Finset.card s)
h_deg_eq : degree f = degree g
hlc : leadingCoeff f = leadingCoeff g
h_eval : ∀ (x : R), x ∈ s → eval x f = eval x g
⊢ f = g
[PROOFSTEP]
rcases eq_or_ne f 0 with rfl | hf
[GOAL]
case inl
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
g : R[X]
s : Finset R
h_deg_le : degree 0 ≤ ↑(Finset.card s)
h_deg_eq : degree 0 = degree g
hlc : leadingCoeff 0 = leadingCoeff g
h_eval : ∀ (x : R), x ∈ s → eval x 0 = eval x g
⊢ 0 = g
[PROOFSTEP]
rwa [degree_zero, eq_comm, degree_eq_bot, eq_comm] at h_deg_eq 
[GOAL]
case inr
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
s : Finset R
h_deg_le : degree f ≤ ↑(Finset.card s)
h_deg_eq : degree f = degree g
hlc : leadingCoeff f = leadingCoeff g
h_eval : ∀ (x : R), x ∈ s → eval x f = eval x g
hf : f ≠ 0
⊢ f = g
[PROOFSTEP]
exact eq_of_degree_sub_lt_of_eval_finset_eq s (lt_of_lt_of_le (degree_sub_lt h_deg_eq hf hlc) h_deg_le) h_eval
[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
ι : Type u_2
v : ι → R
s : Finset ι
hvs : Set.InjOn v ↑s
degree_f_lt : degree f < ↑(card s)
eval_f : ∀ (i : ι), i ∈ s → eval (v i) f = 0
⊢ f = 0
[PROOFSTEP]
classical
rw [← card_image_of_injOn hvs] at degree_f_lt 
refine' eq_zero_of_degree_lt_of_eval_finset_eq_zero _ degree_f_lt _
intro x hx
rcases mem_image.mp hx with ⟨_, hj, rfl⟩
exact eval_f _ hj
[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
ι : Type u_2
v : ι → R
s : Finset ι
hvs : Set.InjOn v ↑s
degree_f_lt : degree f < ↑(card s)
eval_f : ∀ (i : ι), i ∈ s → eval (v i) f = 0
⊢ f = 0
[PROOFSTEP]
rw [← card_image_of_injOn hvs] at degree_f_lt 
[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
ι : Type u_2
v : ι → R
s : Finset ι
hvs : Set.InjOn v ↑s
degree_f_lt : degree f < ↑(card (image v s))
eval_f : ∀ (i : ι), i ∈ s → eval (v i) f = 0
⊢ f = 0
[PROOFSTEP]
refine' eq_zero_of_degree_lt_of_eval_finset_eq_zero _ degree_f_lt _
[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
ι : Type u_2
v : ι → R
s : Finset ι
hvs : Set.InjOn v ↑s
degree_f_lt : degree f < ↑(card (image v s))
eval_f : ∀ (i : ι), i ∈ s → eval (v i) f = 0
⊢ ∀ (x : R), x ∈ image v s → eval x f = 0
[PROOFSTEP]
intro x hx
[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
ι : Type u_2
v : ι → R
s : Finset ι
hvs : Set.InjOn v ↑s
degree_f_lt : degree f < ↑(card (image v s))
eval_f : ∀ (i : ι), i ∈ s → eval (v i) f = 0
x : R
hx : x ∈ image v s
⊢ eval x f = 0
[PROOFSTEP]
rcases mem_image.mp hx with ⟨_, hj, rfl⟩
[GOAL]
case intro.intro
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
ι : Type u_2
v : ι → R
s : Finset ι
hvs : Set.InjOn v ↑s
degree_f_lt : degree f < ↑(card (image v s))
eval_f : ∀ (i : ι), i ∈ s → eval (v i) f = 0
w✝ : ι
hj : w✝ ∈ s
hx : v w✝ ∈ image v s
⊢ eval (v w✝) f = 0
[PROOFSTEP]
exact eval_f _ hj
[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
ι : Type u_2
v : ι → R
s : Finset ι
hvs : Set.InjOn v ↑s
degree_fg_lt : degree (f - g) < ↑(card s)
eval_fg : ∀ (i : ι), i ∈ s → eval (v i) f = eval (v i) g
⊢ f = g
[PROOFSTEP]
rw [← sub_eq_zero]
[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
ι : Type u_2
v : ι → R
s : Finset ι
hvs : Set.InjOn v ↑s
degree_fg_lt : degree (f - g) < ↑(card s)
eval_fg : ∀ (i : ι), i ∈ s → eval (v i) f = eval (v i) g
⊢ f - g = 0
[PROOFSTEP]
refine' eq_zero_of_degree_lt_of_eval_index_eq_zero _ hvs degree_fg_lt _
[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
ι : Type u_2
v : ι → R
s : Finset ι
hvs : Set.InjOn v ↑s
degree_fg_lt : degree (f - g) < ↑(card s)
eval_fg : ∀ (i : ι), i ∈ s → eval (v i) f = eval (v i) g
⊢ ∀ (i : ι), i ∈ s → eval (v i) (f - g) = 0
[PROOFSTEP]
simp_rw [eval_sub, sub_eq_zero]
[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
ι : Type u_2
v : ι → R
s : Finset ι
hvs : Set.InjOn v ↑s
degree_fg_lt : degree (f - g) < ↑(card s)
eval_fg : ∀ (i : ι), i ∈ s → eval (v i) f = eval (v i) g
⊢ ∀ (i : ι), i ∈ s → eval (v i) f = eval (v i) g
[PROOFSTEP]
exact eval_fg
[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
ι : Type u_2
v : ι → R
s : Finset ι
hvs : Set.InjOn v ↑s
degree_f_lt : degree f < ↑(card s)
degree_g_lt : degree g < ↑(card s)
eval_fg : ∀ (i : ι), i ∈ s → eval (v i) f = eval (v i) g
⊢ f = g
[PROOFSTEP]
refine' eq_of_degree_sub_lt_of_eval_index_eq _ hvs _ eval_fg
[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
ι : Type u_2
v : ι → R
s : Finset ι
hvs : Set.InjOn v ↑s
degree_f_lt : degree f < ↑(card s)
degree_g_lt : degree g < ↑(card s)
eval_fg : ∀ (i : ι), i ∈ s → eval (v i) f = eval (v i) g
⊢ degree (f - g) < ↑(card s)
[PROOFSTEP]
rw [← mem_degreeLT] at degree_f_lt degree_g_lt ⊢
[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
ι : Type u_2
v : ι → R
s : Finset ι
hvs : Set.InjOn v ↑s
degree_f_lt : f ∈ degreeLT R (card s)
degree_g_lt : g ∈ degreeLT R (card s)
eval_fg : ∀ (i : ι), i ∈ s → eval (v i) f = eval (v i) g
⊢ f - g ∈ degreeLT R (card s)
[PROOFSTEP]
exact Submodule.sub_mem _ degree_f_lt degree_g_lt
[GOAL]
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
ι : Type u_2
v : ι → R
s : Finset ι
hvs : Set.InjOn v ↑s
h_deg_le : degree f ≤ ↑(card s)
h_deg_eq : degree f = degree g
hlc : leadingCoeff f = leadingCoeff g
h_eval : ∀ (i : ι), i ∈ s → eval (v i) f = eval (v i) g
⊢ f = g
[PROOFSTEP]
rcases eq_or_ne f 0 with rfl | hf
[GOAL]
case inl
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
g : R[X]
ι : Type u_2
v : ι → R
s : Finset ι
hvs : Set.InjOn v ↑s
h_deg_le : degree 0 ≤ ↑(card s)
h_deg_eq : degree 0 = degree g
hlc : leadingCoeff 0 = leadingCoeff g
h_eval : ∀ (i : ι), i ∈ s → eval (v i) 0 = eval (v i) g
⊢ 0 = g
[PROOFSTEP]
rwa [degree_zero, eq_comm, degree_eq_bot, eq_comm] at h_deg_eq 
[GOAL]
case inr
R : Type u_1
inst✝¹ : CommRing R
inst✝ : IsDomain R
f g : R[X]
ι : Type u_2
v : ι → R
s : Finset ι
hvs : Set.InjOn v ↑s
h_deg_le : degree f ≤ ↑(card s)
h_deg_eq : degree f = degree g
hlc : leadingCoeff f = leadingCoeff g
h_eval : ∀ (i : ι), i ∈ s → eval (v i) f = eval (v i) g
hf : f ≠ 0
⊢ f = g
[PROOFSTEP]
exact eq_of_degree_sub_lt_of_eval_index_eq s hvs (lt_of_lt_of_le (degree_sub_lt h_deg_eq hf hlc) h_deg_le) h_eval
[GOAL]
F : Type u_1
inst✝ : Field F
x y : F
⊢ basisDivisor x x = 0
[PROOFSTEP]
simp only [basisDivisor, sub_self, inv_zero, map_zero, zero_mul]
[GOAL]
F : Type u_1
inst✝ : Field F
x y : F
hxy : basisDivisor x y = 0
⊢ x = y
[PROOFSTEP]
simp_rw [basisDivisor, mul_eq_zero, X_sub_C_ne_zero, or_false_iff, C_eq_zero, inv_eq_zero, sub_eq_zero] at hxy 
[GOAL]
F : Type u_1
inst✝ : Field F
x y : F
hxy : x = y
⊢ x = y
[PROOFSTEP]
exact hxy
[GOAL]
F : Type u_1
inst✝ : Field F
x y : F
⊢ basisDivisor x y ≠ 0 ↔ x ≠ y
[PROOFSTEP]
rw [Ne.def, basisDivisor_eq_zero_iff]
[GOAL]
F : Type u_1
inst✝ : Field F
x y : F
hxy : x ≠ y
⊢ degree (basisDivisor x y) = 1
[PROOFSTEP]
rw [basisDivisor, degree_mul, degree_X_sub_C, degree_C, zero_add]
[GOAL]
F : Type u_1
inst✝ : Field F
x y : F
hxy : x ≠ y
⊢ (x - y)⁻¹ ≠ 0
[PROOFSTEP]
exact inv_ne_zero (sub_ne_zero_of_ne hxy)
[GOAL]
F : Type u_1
inst✝ : Field F
x y : F
⊢ degree (basisDivisor x x) = ⊥
[PROOFSTEP]
rw [basisDivisor_self, degree_zero]
[GOAL]
F : Type u_1
inst✝ : Field F
x y : F
⊢ natDegree (basisDivisor x x) = 0
[PROOFSTEP]
rw [basisDivisor_self, natDegree_zero]
[GOAL]
F : Type u_1
inst✝ : Field F
x y : F
⊢ eval y (basisDivisor x y) = 0
[PROOFSTEP]
simp only [basisDivisor, eval_mul, eval_C, eval_sub, eval_X, sub_self, mul_zero]
[GOAL]
F : Type u_1
inst✝ : Field F
x y : F
hxy : x ≠ y
⊢ eval x (basisDivisor x y) = 1
[PROOFSTEP]
simp only [basisDivisor, eval_mul, eval_C, eval_sub, eval_X]
[GOAL]
F : Type u_1
inst✝ : Field F
x y : F
hxy : x ≠ y
⊢ (x - y)⁻¹ * (x - y) = 1
[PROOFSTEP]
exact inv_mul_cancel (sub_ne_zero_of_ne hxy)
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i✝ j i : ι
⊢ Lagrange.basis {i} v i = 1
[PROOFSTEP]
rw [Lagrange.basis, erase_singleton, prod_empty]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j : ι
hij : i ≠ j
⊢ Lagrange.basis {i, j} v i = basisDivisor (v i) (v j)
[PROOFSTEP]
simp only [Lagrange.basis, hij, erase_insert_eq_erase, erase_eq_of_not_mem, mem_singleton, not_false_iff,
  prod_singleton]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j : ι
hij : i ≠ j
⊢ Lagrange.basis {i, j} v j = basisDivisor (v j) (v i)
[PROOFSTEP]
rw [pair_comm]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j : ι
hij : i ≠ j
⊢ Lagrange.basis {j, i} v j = basisDivisor (v j) (v i)
[PROOFSTEP]
exact basis_pair_left hij.symm
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j : ι
hvs : Set.InjOn v ↑s
hi : i ∈ s
⊢ Lagrange.basis s v i ≠ 0
[PROOFSTEP]
simp_rw [Lagrange.basis, prod_ne_zero_iff, Ne.def, mem_erase]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j : ι
hvs : Set.InjOn v ↑s
hi : i ∈ s
⊢ ∀ (a : ι), a ≠ i ∧ a ∈ s → ¬basisDivisor (v i) (v a) = 0
[PROOFSTEP]
rintro j ⟨hij, hj⟩
[GOAL]
case intro
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j✝ : ι
hvs : Set.InjOn v ↑s
hi : i ∈ s
j : ι
hij : j ≠ i
hj : j ∈ s
⊢ ¬basisDivisor (v i) (v j) = 0
[PROOFSTEP]
rw [basisDivisor_eq_zero_iff, hvs.eq_iff hi hj]
[GOAL]
case intro
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j✝ : ι
hvs : Set.InjOn v ↑s
hi : i ∈ s
j : ι
hij : j ≠ i
hj : j ∈ s
⊢ ¬i = j
[PROOFSTEP]
exact hij.symm
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j : ι
hvs : Set.InjOn v ↑s
hi : i ∈ s
⊢ eval (v i) (Lagrange.basis s v i) = 1
[PROOFSTEP]
rw [Lagrange.basis, eval_prod]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j : ι
hvs : Set.InjOn v ↑s
hi : i ∈ s
⊢ ∏ j in Finset.erase s i, eval (v i) (basisDivisor (v i) (v j)) = 1
[PROOFSTEP]
refine' prod_eq_one fun j H => _
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j✝ : ι
hvs : Set.InjOn v ↑s
hi : i ∈ s
j : ι
H : j ∈ Finset.erase s i
⊢ eval (v i) (basisDivisor (v i) (v j)) = 1
[PROOFSTEP]
rw [eval_basisDivisor_left_of_ne]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j✝ : ι
hvs : Set.InjOn v ↑s
hi : i ∈ s
j : ι
H : j ∈ Finset.erase s i
⊢ v i ≠ v j
[PROOFSTEP]
rcases mem_erase.mp H with ⟨hij, hj⟩
[GOAL]
case intro
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j✝ : ι
hvs : Set.InjOn v ↑s
hi : i ∈ s
j : ι
H : j ∈ Finset.erase s i
hij : j ≠ i
hj : j ∈ s
⊢ v i ≠ v j
[PROOFSTEP]
exact mt (hvs hi hj) hij.symm
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j : ι
hij : i ≠ j
hj : j ∈ s
⊢ eval (v j) (Lagrange.basis s v i) = 0
[PROOFSTEP]
simp_rw [Lagrange.basis, eval_prod, prod_eq_zero_iff]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j : ι
hij : i ≠ j
hj : j ∈ s
⊢ ∃ a, a ∈ Finset.erase s i ∧ eval (v j) (basisDivisor (v i) (v a)) = 0
[PROOFSTEP]
exact ⟨j, ⟨mem_erase.mpr ⟨hij.symm, hj⟩, eval_basisDivisor_right⟩⟩
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j : ι
hvs : Set.InjOn v ↑s
hi : i ∈ s
⊢ natDegree (Lagrange.basis s v i) = card s - 1
[PROOFSTEP]
have H : ∀ j, j ∈ s.erase i → basisDivisor (v i) (v j) ≠ 0 :=
  by
  simp_rw [Ne.def, mem_erase, basisDivisor_eq_zero_iff]
  exact fun j ⟨hij₁, hj⟩ hij₂ => hij₁ (hvs hj hi hij₂.symm)
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j : ι
hvs : Set.InjOn v ↑s
hi : i ∈ s
⊢ ∀ (j : ι), j ∈ Finset.erase s i → basisDivisor (v i) (v j) ≠ 0
[PROOFSTEP]
simp_rw [Ne.def, mem_erase, basisDivisor_eq_zero_iff]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j : ι
hvs : Set.InjOn v ↑s
hi : i ∈ s
⊢ ∀ (j : ι), j ≠ i ∧ j ∈ s → ¬v i = v j
[PROOFSTEP]
exact fun j ⟨hij₁, hj⟩ hij₂ => hij₁ (hvs hj hi hij₂.symm)
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j : ι
hvs : Set.InjOn v ↑s
hi : i ∈ s
H : ∀ (j : ι), j ∈ Finset.erase s i → basisDivisor (v i) (v j) ≠ 0
⊢ natDegree (Lagrange.basis s v i) = card s - 1
[PROOFSTEP]
rw [← card_erase_of_mem hi, card_eq_sum_ones]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j : ι
hvs : Set.InjOn v ↑s
hi : i ∈ s
H : ∀ (j : ι), j ∈ Finset.erase s i → basisDivisor (v i) (v j) ≠ 0
⊢ natDegree (Lagrange.basis s v i) = ∑ x in Finset.erase s i, 1
[PROOFSTEP]
convert natDegree_prod _ _ H using 1
[GOAL]
case h.e'_3
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j : ι
hvs : Set.InjOn v ↑s
hi : i ∈ s
H : ∀ (j : ι), j ∈ Finset.erase s i → basisDivisor (v i) (v j) ≠ 0
⊢ ∑ x in Finset.erase s i, 1 = ∑ i_1 in Finset.erase s i, natDegree (basisDivisor (v i) (v i_1))
[PROOFSTEP]
refine' sum_congr rfl fun j hj => (natDegree_basisDivisor_of_ne _).symm
[GOAL]
case h.e'_3
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j✝ : ι
hvs : Set.InjOn v ↑s
hi : i ∈ s
H : ∀ (j : ι), j ∈ Finset.erase s i → basisDivisor (v i) (v j) ≠ 0
j : ι
hj : j ∈ Finset.erase s i
⊢ v i ≠ v j
[PROOFSTEP]
rw [Ne.def, ← basisDivisor_eq_zero_iff]
[GOAL]
case h.e'_3
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j✝ : ι
hvs : Set.InjOn v ↑s
hi : i ∈ s
H : ∀ (j : ι), j ∈ Finset.erase s i → basisDivisor (v i) (v j) ≠ 0
j : ι
hj : j ∈ Finset.erase s i
⊢ ¬basisDivisor (v i) (v j) = 0
[PROOFSTEP]
exact H _ hj
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j : ι
hvs : Set.InjOn v ↑s
hi : i ∈ s
⊢ degree (Lagrange.basis s v i) = ↑(card s - 1)
[PROOFSTEP]
rw [degree_eq_natDegree (basis_ne_zero hvs hi), natDegree_basis hvs hi]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j : ι
hvs : Set.InjOn v ↑s
hs : Finset.Nonempty s
⊢ ∑ j in s, Lagrange.basis s v j = 1
[PROOFSTEP]
refine' eq_of_degrees_lt_of_eval_index_eq s hvs (lt_of_le_of_lt (degree_sum_le _ _) _) _ _
[GOAL]
case refine'_1
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j : ι
hvs : Set.InjOn v ↑s
hs : Finset.Nonempty s
⊢ (sup s fun b => degree (Lagrange.basis s v b)) < ↑(card s)
[PROOFSTEP]
rw [Nat.cast_withBot, Finset.sup_lt_iff (WithBot.bot_lt_coe s.card)]
[GOAL]
case refine'_1
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j : ι
hvs : Set.InjOn v ↑s
hs : Finset.Nonempty s
⊢ ∀ (b : ι), b ∈ s → degree (Lagrange.basis s v b) < ↑(card s)
[PROOFSTEP]
intro i hi
[GOAL]
case refine'_1
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i✝ j : ι
hvs : Set.InjOn v ↑s
hs : Finset.Nonempty s
i : ι
hi : i ∈ s
⊢ degree (Lagrange.basis s v i) < ↑(card s)
[PROOFSTEP]
rw [degree_basis hvs hi, Nat.cast_withBot, WithBot.coe_lt_coe]
[GOAL]
case refine'_1
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i✝ j : ι
hvs : Set.InjOn v ↑s
hs : Finset.Nonempty s
i : ι
hi : i ∈ s
⊢ card s - 1 < card s
[PROOFSTEP]
exact Nat.pred_lt (card_ne_zero_of_mem hi)
[GOAL]
case refine'_2
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j : ι
hvs : Set.InjOn v ↑s
hs : Finset.Nonempty s
⊢ degree 1 < ↑(card s)
[PROOFSTEP]
rw [degree_one, ← WithBot.coe_zero, Nat.cast_withBot, WithBot.coe_lt_coe]
[GOAL]
case refine'_2
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j : ι
hvs : Set.InjOn v ↑s
hs : Finset.Nonempty s
⊢ 0 < card s
[PROOFSTEP]
exact Nonempty.card_pos hs
[GOAL]
case refine'_3
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j : ι
hvs : Set.InjOn v ↑s
hs : Finset.Nonempty s
⊢ ∀ (i : ι), i ∈ s → eval (v i) (∑ j in s, Lagrange.basis s v j) = eval (v i) 1
[PROOFSTEP]
intro i hi
[GOAL]
case refine'_3
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i✝ j : ι
hvs : Set.InjOn v ↑s
hs : Finset.Nonempty s
i : ι
hi : i ∈ s
⊢ eval (v i) (∑ j in s, Lagrange.basis s v j) = eval (v i) 1
[PROOFSTEP]
rw [eval_finset_sum, eval_one, ← add_sum_erase _ _ hi, eval_basis_self hvs hi, add_right_eq_self]
[GOAL]
case refine'_3
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i✝ j : ι
hvs : Set.InjOn v ↑s
hs : Finset.Nonempty s
i : ι
hi : i ∈ s
⊢ ∑ x in Finset.erase s i, eval (v i) (Lagrange.basis s v x) = 0
[PROOFSTEP]
refine' sum_eq_zero fun j hj => _
[GOAL]
case refine'_3
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i✝ j✝ : ι
hvs : Set.InjOn v ↑s
hs : Finset.Nonempty s
i : ι
hi : i ∈ s
j : ι
hj : j ∈ Finset.erase s i
⊢ eval (v i) (Lagrange.basis s v j) = 0
[PROOFSTEP]
rcases mem_erase.mp hj with ⟨hij, _⟩
[GOAL]
case refine'_3.intro
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i✝ j✝ : ι
hvs : Set.InjOn v ↑s
hs : Finset.Nonempty s
i : ι
hi : i ∈ s
j : ι
hj : j ∈ Finset.erase s i
hij : j ≠ i
right✝ : j ∈ s
⊢ eval (v i) (Lagrange.basis s v j) = 0
[PROOFSTEP]
rw [eval_basis_of_ne hij hi]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j : ι
x y : F
hxy : x ≠ y
⊢ basisDivisor x y + basisDivisor y x = 1
[PROOFSTEP]
classical rw [← sum_basis (Set.injOn_of_injective Function.injective_id _) ⟨x, mem_insert_self _ { y }⟩,
  sum_insert (not_mem_singleton.mpr hxy), sum_singleton, basis_pair_left hxy, basis_pair_right hxy, id, id]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s : Finset ι
v : ι → F
i j : ι
x y : F
hxy : x ≠ y
⊢ basisDivisor x y + basisDivisor y x = 1
[PROOFSTEP]
rw [← sum_basis (Set.injOn_of_injective Function.injective_id _) ⟨x, mem_insert_self _ { y }⟩,
  sum_insert (not_mem_singleton.mpr hxy), sum_singleton, basis_pair_left hxy, basis_pair_right hxy, id, id]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s✝ t : Finset ι
i j : ι
v✝ r r' : ι → F
s : Finset ι
v f g : ι → F
⊢ (fun r => ∑ i in s, ↑C (r i) * Lagrange.basis s v i) (f + g) =
    (fun r => ∑ i in s, ↑C (r i) * Lagrange.basis s v i) f + (fun r => ∑ i in s, ↑C (r i) * Lagrange.basis s v i) g
[PROOFSTEP]
simp_rw [← Finset.sum_add_distrib]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s✝ t : Finset ι
i j : ι
v✝ r r' : ι → F
s : Finset ι
v f g : ι → F
⊢ ∑ x in s, ↑C ((f + g) x) * Lagrange.basis s v x =
    ∑ x in s, (↑C (f x) * Lagrange.basis s v x + ↑C (g x) * Lagrange.basis s v x)
[PROOFSTEP]
have h :
  (fun x => C (f x) * Lagrange.basis s v x + C (g x) * Lagrange.basis s v x) =
    (fun x => C ((f + g) x) * Lagrange.basis s v x) :=
  by simp_rw [← add_mul, ← C_add, Pi.add_apply]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s✝ t : Finset ι
i j : ι
v✝ r r' : ι → F
s : Finset ι
v f g : ι → F
⊢ (fun x => ↑C (f x) * Lagrange.basis s v x + ↑C (g x) * Lagrange.basis s v x) = fun x =>
    ↑C ((f + g) x) * Lagrange.basis s v x
[PROOFSTEP]
simp_rw [← add_mul, ← C_add, Pi.add_apply]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s✝ t : Finset ι
i j : ι
v✝ r r' : ι → F
s : Finset ι
v f g : ι → F
h :
  (fun x => ↑C (f x) * Lagrange.basis s v x + ↑C (g x) * Lagrange.basis s v x) = fun x =>
    ↑C ((f + g) x) * Lagrange.basis s v x
⊢ ∑ x in s, ↑C ((f + g) x) * Lagrange.basis s v x =
    ∑ x in s, (↑C (f x) * Lagrange.basis s v x + ↑C (g x) * Lagrange.basis s v x)
[PROOFSTEP]
rw [h]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s✝ t : Finset ι
i j : ι
v✝ r r' : ι → F
s : Finset ι
v : ι → F
c : F
f : ι → F
⊢ AddHom.toFun
      { toFun := fun r => ∑ i in s, ↑C (r i) * Lagrange.basis s v i,
        map_add' :=
          (_ :
            ∀ (f g : ι → F),
              (fun r => ∑ i in s, ↑C (r i) * Lagrange.basis s v i) (f + g) =
                (fun r => ∑ i in s, ↑C (r i) * Lagrange.basis s v i) f +
                  (fun r => ∑ i in s, ↑C (r i) * Lagrange.basis s v i) g) }
      (c • f) =
    ↑(RingHom.id F) c •
      AddHom.toFun
        { toFun := fun r => ∑ i in s, ↑C (r i) * Lagrange.basis s v i,
          map_add' :=
            (_ :
              ∀ (f g : ι → F),
                (fun r => ∑ i in s, ↑C (r i) * Lagrange.basis s v i) (f + g) =
                  (fun r => ∑ i in s, ↑C (r i) * Lagrange.basis s v i) f +
                    (fun r => ∑ i in s, ↑C (r i) * Lagrange.basis s v i) g) }
        f
[PROOFSTEP]
simp_rw [Finset.smul_sum, C_mul', smul_smul, Pi.smul_apply, RingHom.id_apply, smul_eq_mul]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
⊢ ↑(interpolate ∅ v) r = 0
[PROOFSTEP]
rw [interpolate_apply, sum_empty]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
⊢ ↑(interpolate {i} v) r = ↑C (r i)
[PROOFSTEP]
rw [interpolate_apply, sum_singleton, basis_singleton, mul_one]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
hs : Finset.Nonempty s
⊢ ↑(interpolate s v) 1 = 1
[PROOFSTEP]
simp_rw [interpolate_apply, Pi.one_apply, map_one, one_mul]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
hs : Finset.Nonempty s
⊢ ∑ x in s, Lagrange.basis s v x = 1
[PROOFSTEP]
exact sum_basis hvs hs
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
hi : i ∈ s
⊢ eval (v i) (↑(interpolate s v) r) = r i
[PROOFSTEP]
rw [interpolate_apply, eval_finset_sum, ← add_sum_erase _ _ hi]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
hi : i ∈ s
⊢ eval (v i) (↑C (r i) * Lagrange.basis s v i) + ∑ x in Finset.erase s i, eval (v i) (↑C (r x) * Lagrange.basis s v x) =
    r i
[PROOFSTEP]
simp_rw [eval_mul, eval_C, eval_basis_self hvs hi, mul_one, add_right_eq_self]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
hi : i ∈ s
⊢ ∑ x in Finset.erase s i, r x * eval (v i) (Lagrange.basis s v x) = 0
[PROOFSTEP]
refine' sum_eq_zero fun j H => _
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j✝ : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
hi : i ∈ s
j : ι
H : j ∈ Finset.erase s i
⊢ r j * eval (v i) (Lagrange.basis s v j) = 0
[PROOFSTEP]
rw [eval_basis_of_ne (mem_erase.mp H).1 hi, mul_zero]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
⊢ degree (↑(interpolate s v) r) ≤ ↑(card s - 1)
[PROOFSTEP]
refine' (degree_sum_le _ _).trans _
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
⊢ (sup s fun b => degree (↑C (r b) * Lagrange.basis s v b)) ≤ ↑(card s - 1)
[PROOFSTEP]
rw [Finset.sup_le_iff]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
⊢ ∀ (b : ι), b ∈ s → degree (↑C (r b) * Lagrange.basis s v b) ≤ ↑(card s - 1)
[PROOFSTEP]
intro i hi
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
i : ι
hi : i ∈ s
⊢ degree (↑C (r i) * Lagrange.basis s v i) ≤ ↑(card s - 1)
[PROOFSTEP]
rw [degree_mul, degree_basis hvs hi]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
i : ι
hi : i ∈ s
⊢ degree (↑C (r i)) + ↑(card s - 1) ≤ ↑(card s - 1)
[PROOFSTEP]
by_cases hr : r i = 0
[GOAL]
case pos
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
i : ι
hi : i ∈ s
hr : r i = 0
⊢ degree (↑C (r i)) + ↑(card s - 1) ≤ ↑(card s - 1)
[PROOFSTEP]
simpa only [hr, map_zero, degree_zero, WithBot.bot_add] using bot_le
[GOAL]
case neg
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
i : ι
hi : i ∈ s
hr : ¬r i = 0
⊢ degree (↑C (r i)) + ↑(card s - 1) ≤ ↑(card s - 1)
[PROOFSTEP]
rw [degree_C hr, zero_add]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
⊢ degree (↑(interpolate s v) r) < ↑(card s)
[PROOFSTEP]
rw [Nat.cast_withBot]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
⊢ degree (↑(interpolate s v) r) < ↑(card s)
[PROOFSTEP]
rcases eq_empty_or_nonempty s with (rfl | h)
[GOAL]
case inl
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑∅
⊢ degree (↑(interpolate ∅ v) r) < ↑(card ∅)
[PROOFSTEP]
rw [interpolate_empty, degree_zero, card_empty]
[GOAL]
case inl
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑∅
⊢ ⊥ < ↑0
[PROOFSTEP]
exact WithBot.bot_lt_coe _
[GOAL]
case inr
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
h : Finset.Nonempty s
⊢ degree (↑(interpolate s v) r) < ↑(card s)
[PROOFSTEP]
refine' lt_of_le_of_lt (degree_interpolate_le _ hvs) _
[GOAL]
case inr
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
h : Finset.Nonempty s
⊢ ↑(card s - 1) < ↑(card s)
[PROOFSTEP]
rw [Nat.cast_withBot, WithBot.coe_lt_coe]
[GOAL]
case inr
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
h : Finset.Nonempty s
⊢ card s - 1 < card s
[PROOFSTEP]
exact Nat.sub_lt (Nonempty.card_pos h) zero_lt_one
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
hi : i ∈ s
⊢ degree (↑(interpolate (Finset.erase s i) v) r) < ↑(card s - 1)
[PROOFSTEP]
rw [← Finset.card_erase_of_mem hi]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
hi : i ∈ s
⊢ degree (↑(interpolate (Finset.erase s i) v) r) < ↑(card (Finset.erase s i))
[PROOFSTEP]
exact degree_interpolate_lt _ (Set.InjOn.mono (coe_subset.mpr (erase_subset _ _)) hvs)
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
hrr' : ↑(interpolate s v) r = ↑(interpolate s v) r'
x✝ : ι
hi : x✝ ∈ s
⊢ r x✝ = r' x✝
[PROOFSTEP]
rw [← eval_interpolate_at_node r hvs hi, hrr', eval_interpolate_at_node r' hvs hi]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j : ι
v r r' : ι → F
hrr' : ∀ (i : ι), i ∈ s → r i = r' i
i : ι
hi : i ∈ s
⊢ ↑C (r i) * Lagrange.basis s v i = ↑C (r' i) * Lagrange.basis s v i
[PROOFSTEP]
rw [hrr' _ hi]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
f : F[X]
hvs : Set.InjOn v ↑s
degree_f_lt : degree f < ↑(card s)
eval_f : ∀ (i : ι), i ∈ s → eval (v i) f = r i
⊢ f = ↑(interpolate s v) r
[PROOFSTEP]
rw [eq_interpolate hvs degree_f_lt]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
f : F[X]
hvs : Set.InjOn v ↑s
degree_f_lt : degree f < ↑(card s)
eval_f : ∀ (i : ι), i ∈ s → eval (v i) f = r i
⊢ (↑(interpolate s v) fun i => eval (v i) f) = ↑(interpolate s v) r
[PROOFSTEP]
exact interpolate_eq_of_values_eq_on _ _ eval_f
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
f : F[X]
hvs : Set.InjOn v ↑s
⊢ (degree f < ↑(card s) ∧ ∀ (i : ι), i ∈ s → eval (v i) f = r i) ↔ f = ↑(interpolate s v) r
[PROOFSTEP]
constructor
[GOAL]
case mp
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
f : F[X]
hvs : Set.InjOn v ↑s
⊢ (degree f < ↑(card s) ∧ ∀ (i : ι), i ∈ s → eval (v i) f = r i) → f = ↑(interpolate s v) r
[PROOFSTEP]
intro h
[GOAL]
case mpr
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
f : F[X]
hvs : Set.InjOn v ↑s
⊢ f = ↑(interpolate s v) r → degree f < ↑(card s) ∧ ∀ (i : ι), i ∈ s → eval (v i) f = r i
[PROOFSTEP]
intro h
[GOAL]
case mp
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
f : F[X]
hvs : Set.InjOn v ↑s
h : degree f < ↑(card s) ∧ ∀ (i : ι), i ∈ s → eval (v i) f = r i
⊢ f = ↑(interpolate s v) r
[PROOFSTEP]
exact eq_interpolate_of_eval_eq _ hvs h.1 h.2
[GOAL]
case mpr
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
f : F[X]
hvs : Set.InjOn v ↑s
h : f = ↑(interpolate s v) r
⊢ degree f < ↑(card s) ∧ ∀ (i : ι), i ∈ s → eval (v i) f = r i
[PROOFSTEP]
rw [h]
[GOAL]
case mpr
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
f : F[X]
hvs : Set.InjOn v ↑s
h : f = ↑(interpolate s v) r
⊢ degree (↑(interpolate s v) r) < ↑(card s) ∧ ∀ (i : ι), i ∈ s → eval (v i) (↑(interpolate s v) r) = r i
[PROOFSTEP]
exact ⟨degree_interpolate_lt _ hvs, fun _ hi => eval_interpolate_at_node _ hvs hi⟩
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
c : F
f : { x // x ∈ degreeLT F (card s) }
⊢ ∀ (x : { x // x ∈ s }),
    AddHom.toFun
        { toFun := fun f i => eval (v ↑i) ↑f,
          map_add' :=
            (_ :
              ∀ (f g : { x // x ∈ degreeLT F (card s) }),
                (fun f i => eval (v ↑i) ↑f) (f + g) = (fun f i => eval (v ↑i) ↑f) f + (fun f i => eval (v ↑i) ↑f) g) }
        (c • f) x =
      (↑(RingHom.id F) c •
          AddHom.toFun
            { toFun := fun f i => eval (v ↑i) ↑f,
              map_add' :=
                (_ :
                  ∀ (f g : { x // x ∈ degreeLT F (card s) }),
                    (fun f i => eval (v ↑i) ↑f) (f + g) =
                      (fun f i => eval (v ↑i) ↑f) f + (fun f i => eval (v ↑i) ↑f) g) }
            f)
        x
[PROOFSTEP]
simp
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
⊢ Function.LeftInverse
    (fun r =>
      { val := ↑(interpolate s v) fun x => if hx : x ∈ s then r { val := x, property := hx } else 0,
        property :=
          (_ :
            (↑(interpolate s v) fun x => if hx : x ∈ s then r { val := x, property := hx } else 0) ∈
              degreeLT F (card s)) })
    {
          toAddHom :=
            { toFun := fun f i => eval (v ↑i) ↑f,
              map_add' :=
                (_ :
                  ∀ (f g : { x // x ∈ degreeLT F (card s) }),
                    (fun f i => eval (v ↑i) ↑f) (f + g) =
                      (fun f i => eval (v ↑i) ↑f) f + (fun f i => eval (v ↑i) ↑f) g) },
          map_smul' :=
            (_ :
              ∀ (c : F) (f : { x // x ∈ degreeLT F (card s) }),
                AddHom.toFun
                    { toFun := fun f i => eval (v ↑i) ↑f,
                      map_add' :=
                        (_ :
                          ∀ (f g : { x // x ∈ degreeLT F (card s) }),
                            (fun f i => eval (v ↑i) ↑f) (f + g) =
                              (fun f i => eval (v ↑i) ↑f) f + (fun f i => eval (v ↑i) ↑f) g) }
                    (c • f) =
                  ↑(RingHom.id F) c •
                    AddHom.toFun
                      { toFun := fun f i => eval (v ↑i) ↑f,
                        map_add' :=
                          (_ :
                            ∀ (f g : { x // x ∈ degreeLT F (card s) }),
                              (fun f i => eval (v ↑i) ↑f) (f + g) =
                                (fun f i => eval (v ↑i) ↑f) f + (fun f i => eval (v ↑i) ↑f) g) }
                      f) }.toAddHom.toFun
[PROOFSTEP]
rintro ⟨f, hf⟩
[GOAL]
case mk
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
f : F[X]
hf : f ∈ degreeLT F (card s)
⊢ (fun r =>
        { val := ↑(interpolate s v) fun x => if hx : x ∈ s then r { val := x, property := hx } else 0,
          property :=
            (_ :
              (↑(interpolate s v) fun x => if hx : x ∈ s then r { val := x, property := hx } else 0) ∈
                degreeLT F (card s)) })
      (AddHom.toFun
        {
            toAddHom :=
              { toFun := fun f i => eval (v ↑i) ↑f,
                map_add' :=
                  (_ :
                    ∀ (f g : { x // x ∈ degreeLT F (card s) }),
                      (fun f i => eval (v ↑i) ↑f) (f + g) =
                        (fun f i => eval (v ↑i) ↑f) f + (fun f i => eval (v ↑i) ↑f) g) },
            map_smul' :=
              (_ :
                ∀ (c : F) (f : { x // x ∈ degreeLT F (card s) }),
                  AddHom.toFun
                      { toFun := fun f i => eval (v ↑i) ↑f,
                        map_add' :=
                          (_ :
                            ∀ (f g : { x // x ∈ degreeLT F (card s) }),
                              (fun f i => eval (v ↑i) ↑f) (f + g) =
                                (fun f i => eval (v ↑i) ↑f) f + (fun f i => eval (v ↑i) ↑f) g) }
                      (c • f) =
                    ↑(RingHom.id F) c •
                      AddHom.toFun
                        { toFun := fun f i => eval (v ↑i) ↑f,
                          map_add' :=
                            (_ :
                              ∀ (f g : { x // x ∈ degreeLT F (card s) }),
                                (fun f i => eval (v ↑i) ↑f) (f + g) =
                                  (fun f i => eval (v ↑i) ↑f) f + (fun f i => eval (v ↑i) ↑f) g) }
                        f) }.toAddHom
        { val := f, property := hf }) =
    { val := f, property := hf }
[PROOFSTEP]
simp only [Subtype.mk_eq_mk, Subtype.coe_mk, dite_eq_ite]
[GOAL]
case mk
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
f : F[X]
hf : f ∈ degreeLT F (card s)
⊢ (↑(interpolate s v) fun x => if x ∈ s then eval (v x) f else 0) = f
[PROOFSTEP]
rw [mem_degreeLT] at hf 
[GOAL]
case mk
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
f : F[X]
hf : degree f < ↑(card s)
⊢ (↑(interpolate s v) fun x => if x ∈ s then eval (v x) f else 0) = f
[PROOFSTEP]
conv => rhs; rw [eq_interpolate hvs hf]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
f : F[X]
hf : degree f < ↑(card s)
| (↑(interpolate s v) fun x => if x ∈ s then eval (v x) f else 0) = f
[PROOFSTEP]
rhs; rw [eq_interpolate hvs hf]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
f : F[X]
hf : degree f < ↑(card s)
| (↑(interpolate s v) fun x => if x ∈ s then eval (v x) f else 0) = f
[PROOFSTEP]
rhs; rw [eq_interpolate hvs hf]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
f : F[X]
hf : degree f < ↑(card s)
| (↑(interpolate s v) fun x => if x ∈ s then eval (v x) f else 0) = f
[PROOFSTEP]
rhs
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
f : F[X]
hf : degree f < ↑(card s)
| f
[PROOFSTEP]
rw [eq_interpolate hvs hf]
[GOAL]
case mk
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
f : F[X]
hf : degree f < ↑(card s)
⊢ (↑(interpolate s v) fun x => if x ∈ s then eval (v x) f else 0) = ↑(interpolate s v) fun i => eval (v i) f
[PROOFSTEP]
exact interpolate_eq_of_values_eq_on _ _ fun _ hi => if_pos hi
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
⊢ Function.RightInverse
    (fun r =>
      { val := ↑(interpolate s v) fun x => if hx : x ∈ s then r { val := x, property := hx } else 0,
        property :=
          (_ :
            (↑(interpolate s v) fun x => if hx : x ∈ s then r { val := x, property := hx } else 0) ∈
              degreeLT F (card s)) })
    {
          toAddHom :=
            { toFun := fun f i => eval (v ↑i) ↑f,
              map_add' :=
                (_ :
                  ∀ (f g : { x // x ∈ degreeLT F (card s) }),
                    (fun f i => eval (v ↑i) ↑f) (f + g) =
                      (fun f i => eval (v ↑i) ↑f) f + (fun f i => eval (v ↑i) ↑f) g) },
          map_smul' :=
            (_ :
              ∀ (c : F) (f : { x // x ∈ degreeLT F (card s) }),
                AddHom.toFun
                    { toFun := fun f i => eval (v ↑i) ↑f,
                      map_add' :=
                        (_ :
                          ∀ (f g : { x // x ∈ degreeLT F (card s) }),
                            (fun f i => eval (v ↑i) ↑f) (f + g) =
                              (fun f i => eval (v ↑i) ↑f) f + (fun f i => eval (v ↑i) ↑f) g) }
                    (c • f) =
                  ↑(RingHom.id F) c •
                    AddHom.toFun
                      { toFun := fun f i => eval (v ↑i) ↑f,
                        map_add' :=
                          (_ :
                            ∀ (f g : { x // x ∈ degreeLT F (card s) }),
                              (fun f i => eval (v ↑i) ↑f) (f + g) =
                                (fun f i => eval (v ↑i) ↑f) f + (fun f i => eval (v ↑i) ↑f) g) }
                      f) }.toAddHom.toFun
[PROOFSTEP]
intro f
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
f : { x // x ∈ s } → F
⊢ AddHom.toFun
      {
          toAddHom :=
            { toFun := fun f i => eval (v ↑i) ↑f,
              map_add' :=
                (_ :
                  ∀ (f g : { x // x ∈ degreeLT F (card s) }),
                    (fun f i => eval (v ↑i) ↑f) (f + g) =
                      (fun f i => eval (v ↑i) ↑f) f + (fun f i => eval (v ↑i) ↑f) g) },
          map_smul' :=
            (_ :
              ∀ (c : F) (f : { x // x ∈ degreeLT F (card s) }),
                AddHom.toFun
                    { toFun := fun f i => eval (v ↑i) ↑f,
                      map_add' :=
                        (_ :
                          ∀ (f g : { x // x ∈ degreeLT F (card s) }),
                            (fun f i => eval (v ↑i) ↑f) (f + g) =
                              (fun f i => eval (v ↑i) ↑f) f + (fun f i => eval (v ↑i) ↑f) g) }
                    (c • f) =
                  ↑(RingHom.id F) c •
                    AddHom.toFun
                      { toFun := fun f i => eval (v ↑i) ↑f,
                        map_add' :=
                          (_ :
                            ∀ (f g : { x // x ∈ degreeLT F (card s) }),
                              (fun f i => eval (v ↑i) ↑f) (f + g) =
                                (fun f i => eval (v ↑i) ↑f) f + (fun f i => eval (v ↑i) ↑f) g) }
                      f) }.toAddHom
      ((fun r =>
          { val := ↑(interpolate s v) fun x => if hx : x ∈ s then r { val := x, property := hx } else 0,
            property :=
              (_ :
                (↑(interpolate s v) fun x => if hx : x ∈ s then r { val := x, property := hx } else 0) ∈
                  degreeLT F (card s)) })
        f) =
    f
[PROOFSTEP]
ext ⟨i, hi⟩
[GOAL]
case h.mk
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
f : { x // x ∈ s } → F
i : ι
hi : i ∈ s
⊢ AddHom.toFun
      {
          toAddHom :=
            { toFun := fun f i => eval (v ↑i) ↑f,
              map_add' :=
                (_ :
                  ∀ (f g : { x // x ∈ degreeLT F (card s) }),
                    (fun f i => eval (v ↑i) ↑f) (f + g) =
                      (fun f i => eval (v ↑i) ↑f) f + (fun f i => eval (v ↑i) ↑f) g) },
          map_smul' :=
            (_ :
              ∀ (c : F) (f : { x // x ∈ degreeLT F (card s) }),
                AddHom.toFun
                    { toFun := fun f i => eval (v ↑i) ↑f,
                      map_add' :=
                        (_ :
                          ∀ (f g : { x // x ∈ degreeLT F (card s) }),
                            (fun f i => eval (v ↑i) ↑f) (f + g) =
                              (fun f i => eval (v ↑i) ↑f) f + (fun f i => eval (v ↑i) ↑f) g) }
                    (c • f) =
                  ↑(RingHom.id F) c •
                    AddHom.toFun
                      { toFun := fun f i => eval (v ↑i) ↑f,
                        map_add' :=
                          (_ :
                            ∀ (f g : { x // x ∈ degreeLT F (card s) }),
                              (fun f i => eval (v ↑i) ↑f) (f + g) =
                                (fun f i => eval (v ↑i) ↑f) f + (fun f i => eval (v ↑i) ↑f) g) }
                      f) }.toAddHom
      ((fun r =>
          { val := ↑(interpolate s v) fun x => if hx : x ∈ s then r { val := x, property := hx } else 0,
            property :=
              (_ :
                (↑(interpolate s v) fun x => if hx : x ∈ s then r { val := x, property := hx } else 0) ∈
                  degreeLT F (card s)) })
        f)
      { val := i, property := hi } =
    f { val := i, property := hi }
[PROOFSTEP]
simp only [Subtype.coe_mk, eval_interpolate_at_node _ hvs hi]
[GOAL]
case h.mk
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
f : { x // x ∈ s } → F
i : ι
hi : i ∈ s
⊢ (if hx : i ∈ s then f { val := i, property := hx } else 0) = f { val := i, property := hi }
[PROOFSTEP]
exact dif_pos hi
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvt : Set.InjOn v ↑t
hs : Finset.Nonempty s
hst : s ⊆ t
⊢ ↑(interpolate t v) r = ∑ i in s, ↑(interpolate (insert i (t \ s)) v) r * Lagrange.basis s v i
[PROOFSTEP]
symm
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvt : Set.InjOn v ↑t
hs : Finset.Nonempty s
hst : s ⊆ t
⊢ ∑ i in s, ↑(interpolate (insert i (t \ s)) v) r * Lagrange.basis s v i = ↑(interpolate t v) r
[PROOFSTEP]
refine' eq_interpolate_of_eval_eq _ hvt (lt_of_le_of_lt (degree_sum_le _ _) _) fun i hi => _
[GOAL]
case refine'_1
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvt : Set.InjOn v ↑t
hs : Finset.Nonempty s
hst : s ⊆ t
⊢ (sup s fun b => degree (↑(interpolate (insert b (t \ s)) v) r * Lagrange.basis s v b)) < ↑(card t)
[PROOFSTEP]
simp_rw [Nat.cast_withBot, Finset.sup_lt_iff (WithBot.bot_lt_coe t.card), degree_mul]
[GOAL]
case refine'_1
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvt : Set.InjOn v ↑t
hs : Finset.Nonempty s
hst : s ⊆ t
⊢ ∀ (b : ι), b ∈ s → degree (↑(interpolate (insert b (t \ s)) v) r) + degree (Lagrange.basis s v b) < ↑(card t)
[PROOFSTEP]
intro i hi
[GOAL]
case refine'_1
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j : ι
v r r' : ι → F
hvt : Set.InjOn v ↑t
hs : Finset.Nonempty s
hst : s ⊆ t
i : ι
hi : i ∈ s
⊢ degree (↑(interpolate (insert i (t \ s)) v) r) + degree (Lagrange.basis s v i) < ↑(card t)
[PROOFSTEP]
have hs : 1 ≤ s.card := Nonempty.card_pos ⟨_, hi⟩
[GOAL]
case refine'_1
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j : ι
v r r' : ι → F
hvt : Set.InjOn v ↑t
hs✝ : Finset.Nonempty s
hst : s ⊆ t
i : ι
hi : i ∈ s
hs : 1 ≤ card s
⊢ degree (↑(interpolate (insert i (t \ s)) v) r) + degree (Lagrange.basis s v i) < ↑(card t)
[PROOFSTEP]
have hst' : s.card ≤ t.card := card_le_of_subset hst
[GOAL]
case refine'_1
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j : ι
v r r' : ι → F
hvt : Set.InjOn v ↑t
hs✝ : Finset.Nonempty s
hst : s ⊆ t
i : ι
hi : i ∈ s
hs : 1 ≤ card s
hst' : card s ≤ card t
⊢ degree (↑(interpolate (insert i (t \ s)) v) r) + degree (Lagrange.basis s v i) < ↑(card t)
[PROOFSTEP]
have H : t.card = 1 + (t.card - s.card) + (s.card - 1) := by
  rw [add_assoc, tsub_add_tsub_cancel hst' hs, ← add_tsub_assoc_of_le (hs.trans hst'), Nat.succ_add_sub_one, zero_add]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j : ι
v r r' : ι → F
hvt : Set.InjOn v ↑t
hs✝ : Finset.Nonempty s
hst : s ⊆ t
i : ι
hi : i ∈ s
hs : 1 ≤ card s
hst' : card s ≤ card t
⊢ card t = 1 + (card t - card s) + (card s - 1)
[PROOFSTEP]
rw [add_assoc, tsub_add_tsub_cancel hst' hs, ← add_tsub_assoc_of_le (hs.trans hst'), Nat.succ_add_sub_one, zero_add]
[GOAL]
case refine'_1
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j : ι
v r r' : ι → F
hvt : Set.InjOn v ↑t
hs✝ : Finset.Nonempty s
hst : s ⊆ t
i : ι
hi : i ∈ s
hs : 1 ≤ card s
hst' : card s ≤ card t
H : card t = 1 + (card t - card s) + (card s - 1)
⊢ degree (↑(interpolate (insert i (t \ s)) v) r) + degree (Lagrange.basis s v i) < ↑(card t)
[PROOFSTEP]
rw [degree_basis (Set.InjOn.mono hst hvt) hi, H, WithBot.coe_add, Nat.cast_withBot,
  WithBot.add_lt_add_iff_right (@WithBot.coe_ne_bot _ (s.card - 1))]
[GOAL]
case refine'_1
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j : ι
v r r' : ι → F
hvt : Set.InjOn v ↑t
hs✝ : Finset.Nonempty s
hst : s ⊆ t
i : ι
hi : i ∈ s
hs : 1 ≤ card s
hst' : card s ≤ card t
H : card t = 1 + (card t - card s) + (card s - 1)
⊢ degree (↑(interpolate (insert i (t \ s)) v) r) < ↑(1 + (card t - card s))
[PROOFSTEP]
convert degree_interpolate_lt _ (hvt.mono (coe_subset.mpr (insert_subset_iff.mpr ⟨hst hi, sdiff_subset _ _⟩)))
[GOAL]
case h.e'_4.h.e'_1
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j : ι
v r r' : ι → F
hvt : Set.InjOn v ↑t
hs✝ : Finset.Nonempty s
hst : s ⊆ t
i : ι
hi : i ∈ s
hs : 1 ≤ card s
hst' : card s ≤ card t
H : card t = 1 + (card t - card s) + (card s - 1)
⊢ 1 + (card t - card s) = card (insert i (t \ s))
[PROOFSTEP]
rw [card_insert_of_not_mem (not_mem_sdiff_of_mem_right hi), card_sdiff hst, add_comm]
[GOAL]
case refine'_2
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j : ι
v r r' : ι → F
hvt : Set.InjOn v ↑t
hs : Finset.Nonempty s
hst : s ⊆ t
i : ι
hi : i ∈ t
⊢ eval (v i) (∑ i in s, ↑(interpolate (insert i (t \ s)) v) r * Lagrange.basis s v i) = r i
[PROOFSTEP]
simp_rw [eval_finset_sum, eval_mul]
[GOAL]
case refine'_2
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j : ι
v r r' : ι → F
hvt : Set.InjOn v ↑t
hs : Finset.Nonempty s
hst : s ⊆ t
i : ι
hi : i ∈ t
⊢ ∑ x in s, eval (v i) (↑(interpolate (insert x (t \ s)) v) r) * eval (v i) (Lagrange.basis s v x) = r i
[PROOFSTEP]
by_cases hi' : i ∈ s
[GOAL]
case pos
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j : ι
v r r' : ι → F
hvt : Set.InjOn v ↑t
hs : Finset.Nonempty s
hst : s ⊆ t
i : ι
hi : i ∈ t
hi' : i ∈ s
⊢ ∑ x in s, eval (v i) (↑(interpolate (insert x (t \ s)) v) r) * eval (v i) (Lagrange.basis s v x) = r i
[PROOFSTEP]
rw [← add_sum_erase _ _ hi', eval_basis_self (hvt.mono hst) hi',
  eval_interpolate_at_node _ (hvt.mono (coe_subset.mpr (insert_subset_iff.mpr ⟨hi, sdiff_subset _ _⟩)))
    (mem_insert_self _ _),
  mul_one, add_right_eq_self]
[GOAL]
case pos
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j : ι
v r r' : ι → F
hvt : Set.InjOn v ↑t
hs : Finset.Nonempty s
hst : s ⊆ t
i : ι
hi : i ∈ t
hi' : i ∈ s
⊢ ∑ x in Finset.erase s i, eval (v i) (↑(interpolate (insert x (t \ s)) v) r) * eval (v i) (Lagrange.basis s v x) = 0
[PROOFSTEP]
refine' sum_eq_zero fun j hj => _
[GOAL]
case pos
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j✝ : ι
v r r' : ι → F
hvt : Set.InjOn v ↑t
hs : Finset.Nonempty s
hst : s ⊆ t
i : ι
hi : i ∈ t
hi' : i ∈ s
j : ι
hj : j ∈ Finset.erase s i
⊢ eval (v i) (↑(interpolate (insert j (t \ s)) v) r) * eval (v i) (Lagrange.basis s v j) = 0
[PROOFSTEP]
rcases mem_erase.mp hj with ⟨hij, _⟩
[GOAL]
case pos.intro
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j✝ : ι
v r r' : ι → F
hvt : Set.InjOn v ↑t
hs : Finset.Nonempty s
hst : s ⊆ t
i : ι
hi : i ∈ t
hi' : i ∈ s
j : ι
hj : j ∈ Finset.erase s i
hij : j ≠ i
right✝ : j ∈ s
⊢ eval (v i) (↑(interpolate (insert j (t \ s)) v) r) * eval (v i) (Lagrange.basis s v j) = 0
[PROOFSTEP]
rw [eval_basis_of_ne hij hi', mul_zero]
[GOAL]
case neg
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j : ι
v r r' : ι → F
hvt : Set.InjOn v ↑t
hs : Finset.Nonempty s
hst : s ⊆ t
i : ι
hi : i ∈ t
hi' : ¬i ∈ s
⊢ ∑ x in s, eval (v i) (↑(interpolate (insert x (t \ s)) v) r) * eval (v i) (Lagrange.basis s v x) = r i
[PROOFSTEP]
have H : (∑ j in s, eval (v i) (Lagrange.basis s v j)) = 1 := by
  rw [← eval_finset_sum, sum_basis (hvt.mono hst) hs, eval_one]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j : ι
v r r' : ι → F
hvt : Set.InjOn v ↑t
hs : Finset.Nonempty s
hst : s ⊆ t
i : ι
hi : i ∈ t
hi' : ¬i ∈ s
⊢ ∑ j in s, eval (v i) (Lagrange.basis s v j) = 1
[PROOFSTEP]
rw [← eval_finset_sum, sum_basis (hvt.mono hst) hs, eval_one]
[GOAL]
case neg
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j : ι
v r r' : ι → F
hvt : Set.InjOn v ↑t
hs : Finset.Nonempty s
hst : s ⊆ t
i : ι
hi : i ∈ t
hi' : ¬i ∈ s
H : ∑ j in s, eval (v i) (Lagrange.basis s v j) = 1
⊢ ∑ x in s, eval (v i) (↑(interpolate (insert x (t \ s)) v) r) * eval (v i) (Lagrange.basis s v x) = r i
[PROOFSTEP]
rw [← mul_one (r i), ← H, mul_sum]
[GOAL]
case neg
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j : ι
v r r' : ι → F
hvt : Set.InjOn v ↑t
hs : Finset.Nonempty s
hst : s ⊆ t
i : ι
hi : i ∈ t
hi' : ¬i ∈ s
H : ∑ j in s, eval (v i) (Lagrange.basis s v j) = 1
⊢ ∑ x in s, eval (v i) (↑(interpolate (insert x (t \ s)) v) r) * eval (v i) (Lagrange.basis s v x) =
    ∑ x in s, r i * eval (v i) (Lagrange.basis s v x)
[PROOFSTEP]
refine' sum_congr rfl fun j hj => _
[GOAL]
case neg
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j✝ : ι
v r r' : ι → F
hvt : Set.InjOn v ↑t
hs : Finset.Nonempty s
hst : s ⊆ t
i : ι
hi : i ∈ t
hi' : ¬i ∈ s
H : ∑ j in s, eval (v i) (Lagrange.basis s v j) = 1
j : ι
hj : j ∈ s
⊢ eval (v i) (↑(interpolate (insert j (t \ s)) v) r) * eval (v i) (Lagrange.basis s v j) =
    r i * eval (v i) (Lagrange.basis s v j)
[PROOFSTEP]
congr
[GOAL]
case neg.e_a
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i✝ j✝ : ι
v r r' : ι → F
hvt : Set.InjOn v ↑t
hs : Finset.Nonempty s
hst : s ⊆ t
i : ι
hi : i ∈ t
hi' : ¬i ∈ s
H : ∑ j in s, eval (v i) (Lagrange.basis s v j) = 1
j : ι
hj : j ∈ s
⊢ eval (v i) (↑(interpolate (insert j (t \ s)) v) r) = r i
[PROOFSTEP]
exact
  eval_interpolate_at_node _ (hvt.mono (insert_subset_iff.mpr ⟨hst hj, sdiff_subset _ _⟩))
    (mem_insert.mpr (Or.inr (mem_sdiff.mpr ⟨hi, hi'⟩)))
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
hi : i ∈ s
hj : j ∈ s
hij : i ≠ j
⊢ ↑(interpolate s v) r =
    ↑(interpolate (Finset.erase s j) v) r * basisDivisor (v i) (v j) +
      ↑(interpolate (Finset.erase s i) v) r * basisDivisor (v j) (v i)
[PROOFSTEP]
rw [interpolate_eq_sum_interpolate_insert_sdiff _ hvs ⟨i, mem_insert_self i { j }⟩ _,
  sum_insert (not_mem_singleton.mpr hij), sum_singleton, basis_pair_left hij, basis_pair_right hij,
  sdiff_insert_insert_of_mem_of_not_mem hi (not_mem_singleton.mpr hij), sdiff_singleton_eq_erase, pair_comm,
  sdiff_insert_insert_of_mem_of_not_mem hj (not_mem_singleton.mpr hij.symm), sdiff_singleton_eq_erase]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
inst✝ : DecidableEq ι
s t : Finset ι
i j : ι
v r r' : ι → F
hvs : Set.InjOn v ↑s
hi : i ∈ s
hj : j ∈ s
hij : i ≠ j
⊢ {i, j} ⊆ s
[PROOFSTEP]
exact insert_subset_iff.mpr ⟨hi, singleton_subset_iff.mpr hj⟩
[GOAL]
F : Type u_1
inst✝ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
⊢ nodal ∅ v = 1
[PROOFSTEP]
rfl
[GOAL]
F : Type u_1
inst✝ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
⊢ degree (nodal s v) = ↑(card s)
[PROOFSTEP]
simp_rw [nodal, degree_prod, degree_X_sub_C, sum_const, Nat.smul_one_eq_coe]
[GOAL]
F : Type u_1
inst✝ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x✝ x : F
⊢ eval x (nodal s v) = ∏ i in s, (x - v i)
[PROOFSTEP]
simp_rw [nodal, eval_prod, eval_sub, eval_X, eval_C]
[GOAL]
F : Type u_1
inst✝ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
hi : i ∈ s
⊢ eval (v i) (nodal s v) = 0
[PROOFSTEP]
rw [eval_nodal, prod_eq_zero_iff]
[GOAL]
F : Type u_1
inst✝ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
hi : i ∈ s
⊢ ∃ a, a ∈ s ∧ v i - v a = 0
[PROOFSTEP]
exact ⟨i, hi, sub_eq_zero_of_eq rfl⟩
[GOAL]
F : Type u_1
inst✝ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
hx : ∀ (i : ι), i ∈ s → x ≠ v i
⊢ eval x (nodal s v) ≠ 0
[PROOFSTEP]
simp_rw [nodal, eval_prod, prod_ne_zero_iff, eval_sub, eval_X, eval_C, sub_ne_zero]
[GOAL]
F : Type u_1
inst✝ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
hx : ∀ (i : ι), i ∈ s → x ≠ v i
⊢ ∀ (a : ι), a ∈ s → x ≠ v a
[PROOFSTEP]
exact hx
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
hi : i ∈ s
⊢ nodal s v = (X - ↑C (v i)) * nodal (Finset.erase s i) v
[PROOFSTEP]
simp_rw [nodal, Finset.mul_prod_erase _ (fun x => X - C (v x)) hi]
[GOAL]
F : Type u_1
inst✝ : Field F
ι : Type u_2
s : Finset ι
v✝ : ι → F
i : ι
r : ι → F
x : F
v : ι → F
hi : i ∈ s
⊢ nodal s v = (X - ↑C (v i)) * ?m.437432 v hi
[PROOFSTEP]
classical exact nodal_eq_mul_nodal_erase hi
[GOAL]
F : Type u_1
inst✝ : Field F
ι : Type u_2
s : Finset ι
v✝ : ι → F
i : ι
r : ι → F
x : F
v : ι → F
hi : i ∈ s
⊢ nodal s v = (X - ↑C (v i)) * ?m.437432 v hi
[PROOFSTEP]
exact nodal_eq_mul_nodal_erase hi
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
hi : i ∈ s
⊢ nodal (Finset.erase s i) v = nodal s v / (X - ↑C (v i))
[PROOFSTEP]
rw [nodal_eq_mul_nodal_erase hi, EuclideanDomain.mul_div_cancel_left]
[GOAL]
case a0
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
hi : i ∈ s
⊢ X - ↑C (v i) ≠ 0
[PROOFSTEP]
exact X_sub_C_ne_zero _
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
hi : ¬i ∈ s
⊢ nodal (insert i s) v = (X - ↑C (v i)) * nodal s v
[PROOFSTEP]
simp_rw [nodal, prod_insert hi]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
⊢ ↑derivative (nodal s v) = ∑ i in s, nodal (Finset.erase s i) v
[PROOFSTEP]
refine' Finset.induction_on s _ fun _ _ hit IH => _
[GOAL]
case refine'_1
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
⊢ ↑derivative (nodal ∅ v) = ∑ i in ∅, nodal (Finset.erase ∅ i) v
[PROOFSTEP]
rw [nodal_empty, derivative_one, sum_empty]
[GOAL]
case refine'_2
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
x✝¹ : ι
x✝ : Finset ι
hit : ¬x✝¹ ∈ x✝
IH : ↑derivative (nodal x✝ v) = ∑ i in x✝, nodal (Finset.erase x✝ i) v
⊢ ↑derivative (nodal (insert x✝¹ x✝) v) = ∑ i in insert x✝¹ x✝, nodal (Finset.erase (insert x✝¹ x✝) i) v
[PROOFSTEP]
rw [nodal_insert_eq_nodal hit, derivative_mul, IH, derivative_sub, derivative_X, derivative_C, sub_zero, one_mul,
  sum_insert hit, mul_sum, erase_insert hit, add_right_inj]
[GOAL]
case refine'_2
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
x✝¹ : ι
x✝ : Finset ι
hit : ¬x✝¹ ∈ x✝
IH : ↑derivative (nodal x✝ v) = ∑ i in x✝, nodal (Finset.erase x✝ i) v
⊢ ∑ x in x✝, (X - ↑C (v x✝¹)) * nodal (Finset.erase x✝ x) v = ∑ x in x✝, nodal (Finset.erase (insert x✝¹ x✝) x) v
[PROOFSTEP]
refine' sum_congr rfl fun j hjt => _
[GOAL]
case refine'_2
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
x✝¹ : ι
x✝ : Finset ι
hit : ¬x✝¹ ∈ x✝
IH : ↑derivative (nodal x✝ v) = ∑ i in x✝, nodal (Finset.erase x✝ i) v
j : ι
hjt : j ∈ x✝
⊢ (X - ↑C (v x✝¹)) * nodal (Finset.erase x✝ j) v = nodal (Finset.erase (insert x✝¹ x✝) j) v
[PROOFSTEP]
rw [nodal_erase_eq_nodal_div (mem_insert_of_mem hjt), nodal_insert_eq_nodal hit,
  EuclideanDomain.mul_div_assoc _ (X_sub_C_dvd_nodal v hjt), nodal_erase_eq_nodal_div hjt]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
hi : i ∈ s
⊢ eval (v i) (↑derivative (nodal s v)) = eval (v i) (nodal (Finset.erase s i) v)
[PROOFSTEP]
rw [derivative_nodal, eval_finset_sum, ← add_sum_erase _ _ hi, add_right_eq_self]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
hi : i ∈ s
⊢ ∑ x in Finset.erase s i, eval (v i) (nodal (Finset.erase s x) v) = 0
[PROOFSTEP]
refine' sum_eq_zero fun j hj => _
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
hi : i ∈ s
j : ι
hj : j ∈ Finset.erase s i
⊢ eval (v i) (nodal (Finset.erase s j) v) = 0
[PROOFSTEP]
simp_rw [nodal, eval_prod, eval_sub, eval_X, eval_C, prod_eq_zero_iff, mem_erase]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
hi : i ∈ s
j : ι
hj : j ∈ Finset.erase s i
⊢ ∃ a, (a ≠ j ∧ a ∈ s) ∧ v i - v a = 0
[PROOFSTEP]
exact ⟨i, ⟨(mem_erase.mp hj).1.symm, hi⟩, sub_eq_zero_of_eq rfl⟩
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
⊢ nodalWeight s v i = (eval (v i) (nodal (Finset.erase s i) v))⁻¹
[PROOFSTEP]
rw [eval_nodal, nodalWeight, prod_inv_distrib]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
hi : i ∈ s
⊢ nodalWeight s v i = (eval (v i) (↑derivative (nodal s v)))⁻¹
[PROOFSTEP]
rw [eval_nodal_derivative_eval_node_eq hi, nodalWeight_eq_eval_nodal_erase_inv]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
hvs : Set.InjOn v ↑s
hi : i ∈ s
⊢ nodalWeight s v i ≠ 0
[PROOFSTEP]
rw [nodalWeight, prod_ne_zero_iff]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
hvs : Set.InjOn v ↑s
hi : i ∈ s
⊢ ∀ (a : ι), a ∈ Finset.erase s i → (v i - v a)⁻¹ ≠ 0
[PROOFSTEP]
intro j hj
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
hvs : Set.InjOn v ↑s
hi : i ∈ s
j : ι
hj : j ∈ Finset.erase s i
⊢ (v i - v j)⁻¹ ≠ 0
[PROOFSTEP]
rcases mem_erase.mp hj with ⟨hij, hj⟩
[GOAL]
case intro
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
hvs : Set.InjOn v ↑s
hi : i ∈ s
j : ι
hj✝ : j ∈ Finset.erase s i
hij : j ≠ i
hj : j ∈ s
⊢ (v i - v j)⁻¹ ≠ 0
[PROOFSTEP]
refine' inv_ne_zero (sub_ne_zero_of_ne (mt (hvs.eq_iff hi hj).mp hij.symm))
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
hi : i ∈ s
⊢ Lagrange.basis s v i = ↑C (nodalWeight s v i) * (nodal s v / (X - ↑C (v i)))
[PROOFSTEP]
simp_rw [Lagrange.basis, basisDivisor, nodalWeight, prod_mul_distrib, map_prod, ← nodal_erase_eq_nodal_div hi, nodal]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
hi : i ∈ s
hxi : x ≠ v i
⊢ eval x (Lagrange.basis s v i) = eval x (nodal s v) * (nodalWeight s v i * (x - v i)⁻¹)
[PROOFSTEP]
rw [mul_comm, basis_eq_prod_sub_inv_mul_nodal_div hi, eval_mul, eval_C, ← nodal_erase_eq_nodal_div hi, eval_nodal,
  eval_nodal, mul_assoc, ← mul_prod_erase _ _ hi, ← mul_assoc (x - v i)⁻¹, inv_mul_cancel (sub_ne_zero_of_ne hxi),
  one_mul]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
j : ι
hj : j ∈ s
⊢ ↑C (r j) * Lagrange.basis s v j = ↑C (nodalWeight s v j) * (nodal s v / (X - ↑C (v j))) * ↑C (r j)
[PROOFSTEP]
rw [mul_comm, basis_eq_prod_sub_inv_mul_nodal_div hj]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
hx : ∀ (i : ι), i ∈ s → x ≠ v i
⊢ eval x (↑(interpolate s v) r) = eval x (nodal s v) * ∑ i in s, nodalWeight s v i * (x - v i)⁻¹ * r i
[PROOFSTEP]
simp_rw [interpolate_apply, mul_sum, eval_finset_sum, eval_mul, eval_C]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
hx : ∀ (i : ι), i ∈ s → x ≠ v i
⊢ ∑ x_1 in s, r x_1 * eval x (Lagrange.basis s v x_1) =
    ∑ x_1 in s, eval x (nodal s v) * (nodalWeight s v x_1 * (x - v x_1)⁻¹ * r x_1)
[PROOFSTEP]
refine' sum_congr rfl fun i hi => _
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i✝ : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
hx : ∀ (i : ι), i ∈ s → x ≠ v i
i : ι
hi : i ∈ s
⊢ r i * eval x (Lagrange.basis s v i) = eval x (nodal s v) * (nodalWeight s v i * (x - v i)⁻¹ * r i)
[PROOFSTEP]
rw [← mul_assoc, mul_comm, eval_basis_not_at_node hi (hx _ hi)]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
hvs : Set.InjOn v ↑s
hx : ∀ (i : ι), i ∈ s → x ≠ v i
hs : Finset.Nonempty s
⊢ eval x (nodal s v) * ∑ i in s, nodalWeight s v i * (x - v i)⁻¹ = 1
[PROOFSTEP]
simpa only [Pi.one_apply, interpolate_one hvs hs, eval_one, mul_one] using (eval_interpolate_not_at_node 1 hx).symm
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
hvs : Set.InjOn v ↑s
hs : Finset.Nonempty s
hx : ∀ (i : ι), i ∈ s → x ≠ v i
⊢ eval x (↑(interpolate s v) r) =
    (∑ i in s, nodalWeight s v i * (x - v i)⁻¹ * r i) / ∑ i in s, nodalWeight s v i * (x - v i)⁻¹
[PROOFSTEP]
rw [← div_one (eval x (interpolate s v r)), ← @eval_one _ _ x, ← interpolate_one hvs hs,
  eval_interpolate_not_at_node r hx, eval_interpolate_not_at_node 1 hx]
[GOAL]
F : Type u_1
inst✝¹ : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝ : DecidableEq ι
hvs : Set.InjOn v ↑s
hs : Finset.Nonempty s
hx : ∀ (i : ι), i ∈ s → x ≠ v i
⊢ (eval x (nodal s fun i => v i) * ∑ i in s, nodalWeight s (fun i => v i) i * (x - v i)⁻¹ * r i) /
      (eval x (nodal s fun i => v i) * ∑ i in s, nodalWeight s (fun i => v i) i * (x - v i)⁻¹ * OfNat.ofNat 1 i) =
    (∑ i in s, nodalWeight s v i * (x - v i)⁻¹ * r i) / ∑ i in s, nodalWeight s v i * (x - v i)⁻¹
[PROOFSTEP]
simp only [mul_div_mul_left _ _ (eval_nodal_not_at_node hx), Pi.one_apply, mul_one]
[GOAL]
F : Type u_1
inst✝² : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝¹ : DecidableEq ι
G : Subgroup Fˣ
inst✝ : Fintype { x // x ∈ G }
⊢ nodal (Set.toFinset ↑G) Units.val = X ^ Fintype.card { x // x ∈ G } - 1
[PROOFSTEP]
have h : degree (1 : F[X]) < degree ((X : F[X]) ^ Fintype.card G) := by simp [Fintype.card_pos]
[GOAL]
F : Type u_1
inst✝² : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝¹ : DecidableEq ι
G : Subgroup Fˣ
inst✝ : Fintype { x // x ∈ G }
⊢ degree 1 < degree (X ^ Fintype.card { x // x ∈ G })
[PROOFSTEP]
simp [Fintype.card_pos]
[GOAL]
F : Type u_1
inst✝² : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝¹ : DecidableEq ι
G : Subgroup Fˣ
inst✝ : Fintype { x // x ∈ G }
h : degree 1 < degree (X ^ Fintype.card { x // x ∈ G })
⊢ nodal (Set.toFinset ↑G) Units.val = X ^ Fintype.card { x // x ∈ G } - 1
[PROOFSTEP]
apply eq_of_degree_le_of_eval_index_eq (v := ((↑) : Fˣ → F)) (G : Set Fˣ).toFinset
[GOAL]
case hvs
F : Type u_1
inst✝² : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝¹ : DecidableEq ι
G : Subgroup Fˣ
inst✝ : Fintype { x // x ∈ G }
h : degree 1 < degree (X ^ Fintype.card { x // x ∈ G })
⊢ Set.InjOn Units.val ↑(Set.toFinset ↑G)
[PROOFSTEP]
exact Set.injOn_of_injective Units.ext _
[GOAL]
case h_deg_le
F : Type u_1
inst✝² : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝¹ : DecidableEq ι
G : Subgroup Fˣ
inst✝ : Fintype { x // x ∈ G }
h : degree 1 < degree (X ^ Fintype.card { x // x ∈ G })
⊢ degree (nodal (Set.toFinset ↑G) Units.val) ≤ ↑(card (Set.toFinset ↑G))
[PROOFSTEP]
simp
[GOAL]
case h_deg_eq
F : Type u_1
inst✝² : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝¹ : DecidableEq ι
G : Subgroup Fˣ
inst✝ : Fintype { x // x ∈ G }
h : degree 1 < degree (X ^ Fintype.card { x // x ∈ G })
⊢ degree (nodal (Set.toFinset ↑G) Units.val) = degree (X ^ Fintype.card { x // x ∈ G } - 1)
[PROOFSTEP]
rw [degree_sub_eq_left_of_degree_lt h, degree_nodal, Set.toFinset_card, degree_pow, degree_X, nsmul_eq_mul, mul_one,
  Nat.cast_inj]
[GOAL]
case h_deg_eq
F : Type u_1
inst✝² : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝¹ : DecidableEq ι
G : Subgroup Fˣ
inst✝ : Fintype { x // x ∈ G }
h : degree 1 < degree (X ^ Fintype.card { x // x ∈ G })
⊢ Fintype.card ↑↑G = Fintype.card { x // x ∈ G }
[PROOFSTEP]
exact rfl
[GOAL]
case hlc
F : Type u_1
inst✝² : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝¹ : DecidableEq ι
G : Subgroup Fˣ
inst✝ : Fintype { x // x ∈ G }
h : degree 1 < degree (X ^ Fintype.card { x // x ∈ G })
⊢ leadingCoeff (nodal (Set.toFinset ↑G) Units.val) = leadingCoeff (X ^ Fintype.card { x // x ∈ G } - 1)
[PROOFSTEP]
rw [nodal_monic, leadingCoeff_sub_of_degree_lt h, monic_X_pow]
[GOAL]
case h_eval
F : Type u_1
inst✝² : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝¹ : DecidableEq ι
G : Subgroup Fˣ
inst✝ : Fintype { x // x ∈ G }
h : degree 1 < degree (X ^ Fintype.card { x // x ∈ G })
⊢ ∀ (i : Fˣ),
    i ∈ Set.toFinset ↑G →
      eval (↑i) (nodal (Set.toFinset ↑G) Units.val) = eval (↑i) (X ^ Fintype.card { x // x ∈ G } - 1)
[PROOFSTEP]
intros i hi
[GOAL]
case h_eval
F : Type u_1
inst✝² : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i✝ : ι
r : ι → F
x : F
inst✝¹ : DecidableEq ι
G : Subgroup Fˣ
inst✝ : Fintype { x // x ∈ G }
h : degree 1 < degree (X ^ Fintype.card { x // x ∈ G })
i : Fˣ
hi : i ∈ Set.toFinset ↑G
⊢ eval (↑i) (nodal (Set.toFinset ↑G) Units.val) = eval (↑i) (X ^ Fintype.card { x // x ∈ G } - 1)
[PROOFSTEP]
rw [eval_nodal_at_node hi]
[GOAL]
case h_eval
F : Type u_1
inst✝² : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i✝ : ι
r : ι → F
x : F
inst✝¹ : DecidableEq ι
G : Subgroup Fˣ
inst✝ : Fintype { x // x ∈ G }
h : degree 1 < degree (X ^ Fintype.card { x // x ∈ G })
i : Fˣ
hi : i ∈ Set.toFinset ↑G
⊢ 0 = eval (↑i) (X ^ Fintype.card { x // x ∈ G } - 1)
[PROOFSTEP]
replace hi : i ∈ G := by simpa using hi
[GOAL]
F : Type u_1
inst✝² : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i✝ : ι
r : ι → F
x : F
inst✝¹ : DecidableEq ι
G : Subgroup Fˣ
inst✝ : Fintype { x // x ∈ G }
h : degree 1 < degree (X ^ Fintype.card { x // x ∈ G })
i : Fˣ
hi : i ∈ Set.toFinset ↑G
⊢ i ∈ G
[PROOFSTEP]
simpa using hi
[GOAL]
case h_eval
F : Type u_1
inst✝² : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i✝ : ι
r : ι → F
x : F
inst✝¹ : DecidableEq ι
G : Subgroup Fˣ
inst✝ : Fintype { x // x ∈ G }
h : degree 1 < degree (X ^ Fintype.card { x // x ∈ G })
i : Fˣ
hi : i ∈ G
⊢ 0 = eval (↑i) (X ^ Fintype.card { x // x ∈ G } - 1)
[PROOFSTEP]
obtain ⟨g, rfl⟩ : ∃ g : G, g.val = i := ⟨⟨i, hi⟩, rfl⟩
[GOAL]
case h_eval.intro
F : Type u_1
inst✝² : Field F
ι : Type u_2
s : Finset ι
v : ι → F
i : ι
r : ι → F
x : F
inst✝¹ : DecidableEq ι
G : Subgroup Fˣ
inst✝ : Fintype { x // x ∈ G }
h : degree 1 < degree (X ^ Fintype.card { x // x ∈ G })
g : { x // x ∈ G }
hi : ↑g ∈ G
⊢ 0 = eval (↑↑g) (X ^ Fintype.card { x // x ∈ G } - 1)
[PROOFSTEP]
simp [← Units.val_pow_eq_pow_val, ← Subgroup.coe_pow G]
