Cost Monotone Multiplicative Power Exists Exponent

The exponent theorem

In mathematics, a completely multiplicative function is one where the value at a product equals the product of the values, such as f(m·n) = f(m)·f(n). The Recognition Science declaration exists_exponent establishes a classification result for a specific class of these functions. It proves that any completely multiplicative function on the positive integers that is also nondecreasing must be a simple power function. In plain terms, there exists a single nonnegative real number c such that f(n) = n^c for every positive integer n. The theorem is a formal statement in the framework's machine-checked library of formal theorems, and it is proved from the defining conditions alone.

The conditions are precise. The function must satisfy three properties: f(1) = 1, multiplicativity for all positive integers, and monotonicity, meaning if m ≤ n then f(m) ≤ f(n). The conclusion covers all positive integers n. The exponent c is guaranteed to be nonnegative. The proof works by comparing powers of n with powers of 2, squeezing the value f(n^k) between f(2^j) and f(2^(j+1)) and letting k grow. This argument, attributed to Howe, establishes that the ratio log(f(n))/log(n) is constant across all bases n.

The theorem has two notable endpoints. The constant function f(n) = 1 realizes the exponent zero, and the identity function f(n) = n realizes the exponent one. Both are shown to satisfy the hypotheses, so the theorem is not vacuous. The monotonicity condition is essential: without it, the Liouville function, which is completely multiplicative but not monotone, is not a power function. The framework uses this result as a step in its broader theory of cost functions, where the exponent governs how recognition costs scale with the size of the input.

What the theorem does not claim is equally important. It does not assert that every completely multiplicative function is a power, only those that are nondecreasing. It does not determine the value of the exponent c from the hypotheses; the exponent is existential, not constructive. It says nothing about functions defined on all integers or on the real numbers, only on the positive integers. The theorem is a classification result within a specific formal system, not a claim about the physical world or about any particular cost function used in applications.

/-- **Erdős's theorem, completely multiplicative case (Howe's proof).** A nondecreasing
completely multiplicative function on the positive integers is a power, with a single
nonnegative real exponent. The degenerate constant function is the exponent zero. -/
theorem exists_exponent (hf : MonotoneMultiplicative f) :
    ∃ c : ℝ, 0 ≤ c ∧ ∀ n : ℕ, 1 ≤ n → f n = (n : ℝ) ^ c := by
  rcases eq_or_lt_of_le (one_le hf (by norm_num : (1 : ℕ) ≤ 2)) with h2 | h2
  · refine ⟨0, le_rfl, fun n hn => ?_⟩
    rw [Real.rpow_zero, eq_one_of_two_eq_one hf h2.symm hn]
  · have hL2 : 0 < Real.log 2 := Real.log_pos (by norm_num)
    have hM2 : 0 < Real.log (f 2) := Real.log_pos h2
    refine ⟨Real.log (f 2) / Real.log 2, le_of_lt (div_pos hM2 hL2), fun n hn => ?_⟩
    rcases eq_or_lt_of_le hn with h1 | h1
    · have hn1 : n = 1 := h1.symm
      subst hn1
      rw [hf.unit, Nat.cast_one, Real.one_rpow]
    · have hn2 : 2 ≤ n := h1
      have hlog := log_ratio hf h2 hn2
      have hnpos : (0 : ℝ) < (n : ℝ) := by
        exact_mod_cast lt_of_lt_of_le Nat.zero_lt_one hn
      have hfpos : 0 < f n := pos hf hn
      rw [Real.rpow_def_of_pos hnpos, ← Real.exp_log hfpos]
      congr 1
      field_simp
      linarith [hlog]

theorem monotoneMultiplicative_const_one : MonotoneMultiplicative (fun _ : ℕ => (1 : ℝ)) where
  unit := rfl
  mul := by intro m n _ _; norm_num
  mono := by intro m n _ _; exact le_rfl

theorem monotoneMultiplicative_id : MonotoneMultiplicative (fun n : ℕ => (n : ℝ)) where
  unit := by norm_num
  mul := by intro m n _ _; push_cast; ring
  mono := by intro m n _ hmn; exact_mod_cast hmn

/-- **Erdős's theorem, completely multiplicative case (Howe's proof).** A nondecreasing
completely multiplicative function on the positive integers is a power, with a single
nonnegative real exponent. The degenerate constant function is the exponent zero. -/
theorem exists_exponent (hf : MonotoneMultiplicative f) :
    ∃ c : ℝ, 0 ≤ c ∧ ∀ n : ℕ, 1 ≤ n → f n = (n : ℝ) ^ c := by
  rcases eq_or_lt_of_le (one_le hf (by norm_num : (1 : ℕ) ≤ 2)) with h2 | h2
  · refine ⟨0, le_rfl, fun n hn => ?_⟩
    rw [Real.rpow_zero, eq_one_of_two_eq_one hf h2.symm hn]
  · have hL2 : 0 < Real.log 2 := Real.log_pos (by norm_num)
    have hM2 : 0 < Real.log (f 2) := Real.log_pos h2
    refine ⟨Real.log (f 2) / Real.log 2, le_of_lt (div_pos hM2 hL2), fun n hn => ?_⟩
    rcases eq_or_lt_of_le hn with h1 | h1
    · have hn1 : n = 1 := h1.symm
      subst hn1
      rw [hf.unit, Nat.cast_one, Real.one_rpow]
    · have hn2 : 2 ≤ n := h1
      have hlog := log_ratio hf h2 hn2
      have hnpos : (0 : ℝ) < (n : ℝ) := by
        exact_mod_cast lt_of_lt_of_le Nat.zero_lt_one hn
      have hfpos : 0 < f n := pos hf hn
      rw [Real.rpow_def_of_pos hnpos, ← Real.exp_log hfpos]
      congr 1
      field_simp
      linarith [hlog]

What this page does not claim

The theorem does not determine the value of the exponent c from the hypotheses. The theorem does not apply to functions defined on all integers or on the real numbers. The theorem is a formal result, not a statement about physical reality.

Verify this page

Every tagged claim above names its theorem. To check one yourself rather than trust this page, elaborate the source module with Lean 4 and audit its axiom basis:

$ lake env lean IndisputableMonolith/Cost/MonotoneMultiplicativePower.lean
expected axiom basis: [propext, Classical.choice, Quot.sound] (the Lean kernel's standard three; no RS-specific axioms)

A page whose claims cannot be reproduced this way does not ship. In production, every anchor links to the exact declaration in the public source release, and this block carries the build receipt for the page itself.

Derived articles

This page is generated by a question-recursion engine: the questions its answers raise become the next pages. The current agenda, with open targets marked red: