Multiples of 1 + X and alternating partial sums

For a finite sequence d₀, …, d_N in a ring, write qₙ = dₙ - dₙ₋₁ + ⋯ ± d₀ = ∑ᵢ₌₀ⁿ (-1)ⁿ⁻ⁱ dᵢ for its alternating partial sums. Telescoping gives the decomposition ∑ᵢ₌₀ᴺ dᵢ Xⁱ = (1 + X) ∑ₙ₌₀ᴺ⁻¹ qₙ Xⁿ + q_N X^N (Polynomial.sum_range_monomial_eq_one_add_X_mul_add_monomial). So 1 + X divides the polynomial exactly when q_N = 0, and then the quotient is ∑ₙ₌₀ᴺ⁻¹ qₙ Xⁿ (Polynomial.sum_range_monomial_eq_one_add_X_mul_iff).

Over ℕ this characterizes the numerical shape of the Morse inequalities. For sequences b, c : ℕ → ℕ, there is a polynomial Q with natural coefficients such that ∑ᵢ₌₀ᴺ cᵢ Xⁱ = ∑ᵢ₌₀ᴺ bᵢ Xⁱ + (1 + X) Q if and only if the alternating partial sums satisfy bₙ - bₙ₋₁ + ⋯ ± b₀ ≤ cₙ - cₙ₋₁ + ⋯ ± c₀ for n < N, with equality for n = N (Polynomial.exists_sum_range_monomial_eq_add_one_add_X_mul_iff). If moreover bᵢ = cᵢ for i > N, then the coefficient of Xⁿ in Q is the difference of the two alternating partial sums in degree n, for every n (Polynomial.coeff_eq_sum_range_neg_one_pow_mul_sub).

References

• J. Milnor, Morse Theory, Annals of Mathematics Studies 51, Princeton University Press, 1963, Section 5.

theorem Polynomial.sum_range_monomial_eq_one_add_X_mul_add_monomial {R : Type u_1} [Ring R] (d : ℕ → R) (N : ℕ) : ∑ i ∈ Finset.range (N + 1), (monomial i) (d i) = (1 + X) * ∑ n ∈ Finset.range N, (monomial n) (∑ i ∈ Finset.range (n + 1), (-1) ^ (n - i) * d i) + (monomial N) (∑ i ∈ Finset.range (N + 1), (-1) ^ (N - i) * d i)

Telescoping against 1 + X. ∑ᵢ₌₀ᴺ dᵢ Xⁱ = (1 + X) ∑ₙ₌₀ᴺ⁻¹ qₙ Xⁿ + q_N X^N, where qₙ = ∑ᵢ₌₀ⁿ (-1)ⁿ⁻ⁱ dᵢ. This is not division with remainder by the monic 1 + X (whose remainder is the constant (-1)ᴺ q_N), but it shows that 1 + X divides the left side when q_N = 0.

theorem Polynomial.sum_range_monomial_eq_one_add_X_mul_iff {R : Type u_1} [Ring R] (d : ℕ → R) (N : ℕ) {Q : Polynomial R} : ∑ i ∈ Finset.range (N + 1), (monomial i) (d i) = (1 + X) * Q ↔ ∑ i ∈ Finset.range (N + 1), (-1) ^ (N - i) * d i = 0 ∧ Q = ∑ n ∈ Finset.range N, (monomial n) (∑ i ∈ Finset.range (n + 1), (-1) ^ (n - i) * d i)

1 + X divides ∑ᵢ₌₀ᴺ dᵢ Xⁱ, with quotient Q, exactly when the alternating sum q_N = ∑ᵢ₌₀ᴺ (-1)ᴺ⁻ⁱ dᵢ vanishes and Q = ∑ₙ₌₀ᴺ⁻¹ qₙ Xⁿ.

theorem Polynomial.exists_sum_range_monomial_eq_add_one_add_X_mul_iff (b c : ℕ → ℕ) (N : ℕ) : (∃ (Q : Polynomial ℕ), ∑ i ∈ Finset.range (N + 1), (monomial i) (c i) = ∑ i ∈ Finset.range (N + 1), (monomial i) (b i) + (1 + X) * Q) ↔ (∀ n < N, ∑ i ∈ Finset.range (n + 1), (-1) ^ (n - i) * ↑(b i) ≤ ∑ i ∈ Finset.range (n + 1), (-1) ^ (n - i) * ↑(c i)) ∧ ∑ i ∈ Finset.range (N + 1), (-1) ^ (N - i) * ↑(b i) = ∑ i ∈ Finset.range (N + 1), (-1) ^ (N - i) * ↑(c i)

Polynomial form of the Morse inequalities. For b, c : ℕ → ℕ, there is a polynomial Q ∈ ℕ[X] with ∑ᵢ₌₀ᴺ cᵢ Xⁱ = ∑ᵢ₌₀ᴺ bᵢ Xⁱ + (1 + X) Q if and only if bₙ - bₙ₋₁ + ⋯ ± b₀ ≤ cₙ - cₙ₋₁ + ⋯ ± c₀ for every n < N, with equality for n = N.

theorem Polynomial.coeff_eq_sum_range_neg_one_pow_mul_sub {b c : ℕ → ℕ} {N : ℕ} {Q : Polynomial ℕ} (h : ∑ i ∈ Finset.range (N + 1), (monomial i) (c i) = ∑ i ∈ Finset.range (N + 1), (monomial i) (b i) + (1 + X) * Q) (hbc : ∀ (i : ℕ), N < i → b i = c i) (n : ℕ) : ↑(Q.coeff n) = ∑ i ∈ Finset.range (n + 1), (-1) ^ (n - i) * ↑(c i) - ∑ i ∈ Finset.range (n + 1), (-1) ^ (n - i) * ↑(b i)

If ∑ᵢ₌₀ᴺ cᵢ Xⁱ = ∑ᵢ₌₀ᴺ bᵢ Xⁱ + (1 + X) Q in ℕ[X], and bᵢ = cᵢ for i > N, then the coefficient of Xⁿ in Q is (cₙ - cₙ₋₁ + ⋯ ± c₀) - (bₙ - bₙ₋₁ + ⋯ ± b₀), for every n.