Add arithmetic functions as values and Dirichlet convolution

[sraaphorst]

Depends on:

• Add arithmetic operations on integer factorizations #230
• Add generic Factorization<A> and integer FactorizationDomain #229

Summary

Add an arithmetic-function abstraction and Dirichlet convolution over positive Kosmos integers.

Issue 2 adds arithmetic-function-style operations on integer factorizations. This issue adds the next layer: arithmetic functions as first-class mathematical values.

Dirichlet convolution should be implemented using divisor enumeration and documented as the number-theoretic specialization of incidence-algebra convolution on the divisibility poset.

Motivation

An arithmetic function is a function:

f : ℕ⁺ → R

where R is some coefficient type.

Many classical identities among arithmetic functions are most naturally expressed using Dirichlet convolution.

For arithmetic functions

f, g : ℕ⁺ → R

the Dirichlet convolution is defined by:

(f * g)(n) = Σ_{d | n} f(d) g(n / d)

Important identities include:

μ * 1 = ε
φ * 1 = id
σₖ = idₖ * 1

This makes arithmetic functions algebraic values rather than isolated computations.

Scope

This issue should target arithmetic functions over positive Kosmos integers, backed by BigInteger or the existing Kosmos positive-integer wrapper.

The coefficient type should be generic where reasonable.

For example:

ArithmeticFunction<R>

where the domain is fixed to positive Kosmos integers and the codomain is R.

This issue should not attempt to define arithmetic functions over arbitrary factorization domains, Euclidean domains, UFDs, or polynomial rings.

This issue should also not introduce p-adic numbers or p-adic arithmetic. The integer (p)-adic valuation from Issue 2 can be exposed as an arithmetic function family if desired, but it is not the primary focus of this issue.

Proposed abstraction

Add an abstraction similar to:

interface ArithmeticFunction<R : Any> {
    fun value(n: BigInteger): R
}

If Kosmos has a PositiveInteger or Natural type, prefer that:

interface ArithmeticFunction<R : Any> {
    fun value(n: PositiveInteger): R
}

Consider adding optional metadata:

interface ArithmeticFunction<R : Any> {
    val properties: ArithmeticFunctionProperties
    fun value(n: PositiveInteger): R
}

The metadata can be deferred if it complicates the first version.

Standard arithmetic-function values

Add standard arithmetic functions as values:

val One: ArithmeticFunction<BigInteger>
val Epsilon: ArithmeticFunction<BigInteger>
val Identity: ArithmeticFunction<BigInteger>

fun PowerIdentity(k: Int): ArithmeticFunction<BigInteger>

val Mobius: ArithmeticFunction<Int>
val Liouville: ArithmeticFunction<Int>
val Totient: ArithmeticFunction<BigInteger>

Exact names and types should follow Kosmos conventions.

The pointwise implementations should delegate to the Factorization<BigInteger> operations from Issue 2 where appropriate.

For example:

Mobius.value(n) = factor(n).mobius()
Liouville.value(n) = factor(n).liouville()
Totient.value(n) = factor(n).eulerTotient()

Optional p-adic valuation function family

If lightweight, expose p-adic valuation as an arithmetic-function family:

fun PadicValuation(p: BigInteger): ArithmeticFunction<Int>

or:

fun valuationAtPrime(p: BigInteger): ArithmeticFunction<Int>

where:

PadicValuation(p).value(n) = v_p(n)

This should delegate to Issue 2:

factor(n).padicValuation(p)

Document that p is expected to be prime.

This optional arithmetic-function value is still just the integer-valued valuation function. It should not imply support for p-adic numbers, p-adic integers, p-adic rationals, or p-adic arithmetic.

If this feels like scope creep, defer this to a later small issue.

Standard definitions

The constant-one function:

1(n) = 1

The convolution identity:

ε(n) = 1 if n = 1
ε(n) = 0 otherwise

The identity function:

id(n) = n

The power identity function:

idₖ(n) = n^k

Dirichlet convolution

Add Dirichlet convolution:

fun <R : Any> dirichletConvolution(
    f: ArithmeticFunction<R>,
    g: ArithmeticFunction<R>,
    semiring: Semiring<R>
): ArithmeticFunction<R>

The implementation should use divisor enumeration:

(f * g)(n) = Σ_{d | n} f(d) g(n / d)

Divisor enumeration may come from:

factor(n).divisors()

or another divisor utility based on integer factorization.

Relationship to Factorization<BigInteger>

This issue should not replace the operations from Issue 2.

Instead, it should layer over them.

The intended relationship is:

Factorization<BigInteger> operations:
  efficient structural computations once a number is factored

ArithmeticFunction values:
  mathematical objects that can be combined by operations such as Dirichlet convolution

For example:

factor(360).mobius()

is a direct computation on an already-known factorization, while:

Mobius.value(360)

is the value of the Möbius arithmetic function at 360.

Both are useful.

Connection to incidence algebras

Document that Dirichlet convolution is incidence-algebra convolution on the positive integers ordered by divisibility.

For a | b, the interval [a, b] corresponds to divisors of b / a.

The classical formula

(f * g)(n) = Σ_{d | n} f(d)g(n/d)

is the specialization of

(F * G)(a, b) = Σ_{a ≤ z ≤ b} F(a, z)G(z, b)

when values depend only on the quotient b / a.

This connects the number-theory layer to the order/incidence-algebra layer.

Arithmetic-function properties

If metadata is included, add something like:

enum class Multiplicativity {
    None,
    Multiplicative,
    CompletelyMultiplicative
}

enum class Additivity {
    None,
    Additive,
    CompletelyAdditive
}

data class ArithmeticFunctionProperties(
    val multiplicativity: Multiplicativity = Multiplicativity.None,
    val additivity: Additivity = Additivity.None
)

Standard properties:

One: completely multiplicative
Epsilon: multiplicative, not completely multiplicative
Identity: completely multiplicative
PowerIdentity(k): completely multiplicative
Mobius: multiplicative, not completely multiplicative
Liouville: completely multiplicative
Totient: multiplicative, not completely multiplicative
PadicValuation(p): completely additive

For (p)-adic valuation:

v_p(ab) = v_p(a) + v_p(b)

so PadicValuation(p) is completely additive as an arithmetic function from positive integers to integers.

Use number-theoretic terminology:

multiplicative:
f(ab) = f(a)f(b) when gcd(a, b) = 1

completely multiplicative:
f(ab) = f(a)f(b) for all a, b

additive:
f(ab) = f(a) + f(b) when gcd(a, b) = 1

completely additive:
f(ab) = f(a) + f(b) for all a, b

Do not use the ring-homomorphism meaning f(x + y) = f(x) + f(y) for this metadata.

Dirichlet inverse

Dirichlet inverse can be left for a later issue.

If added later, it should require a coefficient Ring<R> or stronger structure rather than merely a Semiring<R>.

The key condition for an arithmetic function f to have a Dirichlet inverse is that f(1) is invertible in the coefficient structure.

This issue should focus on convolution first.

Tests

Test identities:

μ * 1 = ε
1 * μ = ε
φ * 1 = id
1 * φ = id
idₖ * 1 = σₖ

Test explicit convolution values for small n.

Examples:

(1 * 1)(n) = τ(n)

since it counts divisors.

Also:

(id * 1)(n) = σ(n)

and more generally:

(idₖ * 1)(n) = σₖ(n)

Test values for n = 1..20.

Suggested implementation tests

For n = 12:

(1 * 1)(12) = 6

because the divisors of 12 are:

1, 2, 3, 4, 6, 12

For n = 12:

(id * 1)(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28

For n = 12:

(μ * 1)(12) = 0

because 12 > 1, so this should agree with ε(12).

For n = 1:

(μ * 1)(1) = 1

which should agree with ε(1).

If PadicValuation(p) is included, test complete additivity:

v_p(ab) = v_p(a) + v_p(b)

For example:

v_2(12 · 20) = v_2(12) + v_2(20) = 2 + 2 = 4

Acceptance criteria

• Add an arithmetic-function abstraction over positive Kosmos integers.
• Use BigInteger or the existing Kosmos positive-integer wrapper as the default domain.
• Add standard arithmetic-function values: one, epsilon, identity, and power identity.
• Add arithmetic-function values for Möbius, Liouville, and Euler totient.
• Ensure arithmetic-function values delegate to Factorization<BigInteger> operations where appropriate.
• Add Dirichlet convolution using divisor enumeration.
• Add tests for classical convolution identities.
• Document the relationship between:
  • Factorization<BigInteger> operations,
  • arithmetic-function values,
  • Dirichlet convolution,
  • incidence algebra over the divisibility poset.
• Optionally add PadicValuation(p) as an arithmetic-function family.
• Do not introduce p-adic numbers or p-adic arithmetic in this issue.