Arithmetic functions

[a1dd0ea6-9300-4f97-bb3c-0f25ba420caf]

This ticket is mainly a playground for ideas (for now). Anyone: Feel free to take over... :)

I would like to see some way to work with exact arithmetic functions. In particular when dealing with series (e.g. Dirichlet series but also other series): If a good implementation of function spaces is around then a series could be stored (in an exact way) by specifying it's coefficient function. I.e. allowing/using arithmetic functions as element constructor arguments for (Dirichlet) series. Also see https://github.com/sagemath/sage-prod/issues/16477 for the Dirichlet series ticket.

Nice subspaces are given by the ring of arithmetic functions with multiplication by convolution. This corresponds to the usual product of the associated Dirichlet series (which acts like a Fourier transform of the arithmetic function). Other (smaller) subspaces are given by multiplicative or completely multiplicative functions.

One other idea might be to use the symbolic ring. Apparently it supports symbolic_sum.

I tried to start with one possible (quick) POC implementation.

Here is a simple example:

sigma3 = ArithmeticFunction(lambda n: sigma(n,3), lambda n,_: "sigma({},3)".format(n), lambda n,_: "\\sigma_{{3}}\\left({}\\right)".format(n))
sigma3^2
show(sigma3^2)
(sigma3^2)(5)

Some issues:

• representations of coefficients / functions
• simplifications of functions/representations: For instance we could group sums into one big sum with many conditions over many summation variables. If summation conditions are handled carefully/abstractly this could allow some powerful simplifications.
• comparisons of functions (very hard!): For functions which are built up from well-defined simple functions this might work by storing them in some abstract syntax tree and using some sophisticated way to compare ASTs (???)
• finding the right way to go about it (categories/etc)
• trivial scalar multiplication: How to make/represent it as simple as possible?

Clearly a lot of the structure comes from the codomain. If it has a ring structure it carries over to the function space and with natural numbers as domain we can define a convolution product. An algebra would also carry over nicely. What's the right general setup for this?

EDIT: This ticket is mainly about the middle column of attachment: dgf-cases.txt Ideal would be if there was a way to translate between different representations (GS,CF,DS).

I'm all ears for suggestions / better alternatives.

CC: @rwst @kcrisman @slel

Component: number theory

Keywords: arithmetic functions

Author: Jonas Jermann

Branch/Commit: u/jj/arith_functions @ 526e1ae

Issue created by migration from https://trac.sagemath.org/ticket/18102

[a1dd0ea6-9300-4f97-bb3c-0f25ba420caf]

Attachment: dgf-cases.txt

Generating series (GS), Coefficient function (CF), Dirichlet series (DS)

[a1dd0ea6-9300-4f97-bb3c-0f25ba420caf]

Description changed:

--- 
+++ 
@@ -20,15 +20,20 @@
 (sigma3^2)(5)

-Main issues I see are: +Some issues:

• representations of coefficients / functions
• simplifications of functions/representations: For instance we could group sums into one big sum with many conditions over many summation variables. If summation conditions are handled carefully/abstractly this could allow some powerful simplifications. -- comparisons of functions (very hard!) +- comparisons of functions (very hard!):
  • For functions which are built up from well-defined simple functions this might work by storing them in
  • some abstract syntax tree and using some sophisticated way to compare ASTs (???)
• finding the right way to go about it (categories/etc)

• trivial scalar multiplication: How to make/represent it as simple as possible?

  Clearly a lot of the structure comes from the codomain. If it has a ring structure it carries over to the function space and with natural numbers as domain we can define a convolution product. An algebra would also carry over nicely. What's the right general setup for this?

+EDIT: This ticket is mainly about the middle column of attachment: dgf-cases.txt +Ideal would be if there was a way to translate between different representations (GS,CF,DS). + I'm all ears for suggestions / better alternatives.

[mantepse]

comment:2

EDIT:

Sorry, wrong ticket (and not much content anyway, I admit).

OLD POST:

I have written (a long time ago) a domain for Dirichlet series in FriCAS. If you install FriCAS (with sage -i fricas, you can find the source in

/sage/local/lib/fricas/target/x86_64-unknown-linux/src/algebra/

[a1dd0ea6-9300-4f97-bb3c-0f25ba420caf]

Description changed:

--- 
+++ 
@@ -7,7 +7,8 @@
 Nice subspaces are given by the ring of arithmetic functions with multiplication by convolution.
 This corresponds to the usual product of the associated Dirichlet series (which acts like a Fourier transform of the arithmetic function).
 Other (smaller) subspaces are given by multiplicative or completely multiplicative functions.
-One idea might be to use the symbolic ring. But it has trouble with "sums" which are absolutely crucial for most operations with arithmetic functions.
+
+One other idea might be to use the symbolic ring. Apparently it supports symbolic_sum.

 I tried to start with one possible (quick) POC implementation.