Waring's problem and figurate numbers

Hilbert–Waring, g(3)=9, Fermat polygonal theorem, polygonal, triangular and polytopic numbers and their sums.

• Lucas-polytopic numbers
• Nicomachus's theorem and its generalizations
• Polygonal numbers
• Fermat polygonal number theorem
• Waring's problem for cubes

TheoremHilbert–Waring theorem#✓fully proved

For every integer \(k \ge 1\) there is a natural number \(g\) such that every natural number \(n\) is a sum of \(g\) \(k\)-th powers of natural numbers, that is, \(n = x_1^k + \dots + x_g^k\) for some \(x_1, \dots, x_g \in \mathbb{N}\).

Proof: We follow Linnik's elementary route as presented in Tim Jameson's notes: a mean-value estimate gives positive Schnirelmann density for a bounded power sumset, which is then an additive basis of finite order by Schnirelmann's inequality.

public theorem hilbert_waring :
    ∀ k : ℕ, 0 < k → ∃ g : ℕ, ∀ n : ℕ, ∃ x : Fin g → ℕ,
      n = Finset.univ.sum fun i => (x i) ^ k

Sources

• D. Hilbert, Beweis für die Darstellbarkeit der ganzen Zahlen durch eine feste Anzahl n-ter Potenzen (Waringsches Problem), Math. Ann. 67 (1909) 281–305; textbook in Vaughan, The Hardy-Littlewood Method; general includes minimal g(k).

Uses 1

Proof usesSchnirelmann's basis theorem

TheoremLegendre's four-triangular-numbers theorem#✓fully proved

For \(k \ge 0\) let \(T_k = k(k+1)/2\) be the \(k\)-th triangular number. For every natural number \(j\), the number of ordered quadruples \((k_1, k_2, k_3, k_4)\) of integers with \(0 \le k_i \le j\) and \(T_{k_1} + T_{k_2} + T_{k_3} + T_{k_4} = j\) equals \(\sigma(2j+1)\), the sum of the positive divisors of \(2j+1\).

The bound \(k_i \le j\) is automatic, since \(T_k \ge k\). Representations using \(T_0 = 0\) are counted, and quadruples that differ only in the order of their entries are counted separately.

public theorem four_triangular_numbers_eq_divisor_sum
    (j : ℕ) :
    Fintype.card { t : Fin 4 → Fin (j + 1) //
      (∑ i, ((t i).val * ((t i).val + 1) / 2)) = j } =
      ∑ d ∈ Nat.divisors (2 * j + 1), d

Sources

• Hartosh Singh Bal and Gaurav Bhatnagar, "Glaisher's Divisors and Infinite Products," Journal of Integer Sequences 27 (2024), Article 24.1.6, Proposition [Legendre] (equation nttriangle-b), lines 738–740, https://cs.uwaterloo.ca/journals/JIS/VOL27/Bhatnagar/bhat4.tex

TheoremWaring's problem for Hurwitz quaternion integers#✓fully proved

Call a rational quaternion a Hurwitz integer if its four coordinates are either all integers or all of the form \(a + \tfrac12\) with \(a\) an integer. For every positive integer \(\ell\) with \(\ell \equiv 1\) or \(\ell \equiv 2 \pmod 3\) there is a natural number \(g\) such that every Hurwitz integer is a sum of at most \(g\) \(\ell\)-th powers of Hurwitz integers.

theorem hurwitz_quaternion_waring_bound
    (ℓ : ℕ) (hℓpos : 0 < ℓ) (hℓmod : ℓ % 3 = 1 ∨ ℓ % 3 = 2) :
    let IsHurwitz : Quaternion ℚ → Prop := fun z =>
      (∃ a b c d : ℤ,
        z.re = (a : ℚ) ∧ z.imI = (b : ℚ) ∧ z.imJ = (c : ℚ) ∧ z.imK = (d : ℚ)) ∨
      (∃ a b c d : ℤ,
        z.re = (a : ℚ) + 1 / 2 ∧ z.imI = (b : ℚ) + 1 / 2 ∧
          z.imJ = (c : ℚ) + 1 / 2 ∧ z.imK = (d : ℚ) + 1 / 2)
    ∃ g : ℕ, ∀ z : Quaternion ℚ, IsHurwitz z →
      ∃ n : ℕ, n ≤ g ∧ ∃ q : Fin n → Quaternion ℚ,
        (∀ i, IsHurwitz (q i)) ∧ ∑ i, (q i) ^ ℓ = z

Sources

• Janyarak Tongsomporn, Nicola Oswald, and Jörn Steuding, "Waring's Problem for Hurwitz Quaternion Integers," Journal of Integer Sequences 22 (2019), Article 19.8.1, Theorem, lines 127–129, https://cs.uwaterloo.ca/journals/JIS/VOL22/Steuding/steuding6.tex

3 fully proved

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.