3
$\begingroup$

I'm writing an app in Nim to search for curious integer identities such as those ones listed on:MathWorld: Divisor Function where it says "curious identities derived using modular theory".

The program doesn't prove the identity but should only give a recommendation of what identities for mathematicians to look into. It does this by simply testing equality of an expression $f(n)$ to zero (over a large set of integers), where $f(n)$ is formed by composing the operators:

  • $+, -, \pmod{k}, \times$
  • $\gcd, \text{lcm}$
  • $\sigma_k(n)$ (divisor function)
  • $\sum_{\text{some set}}$
  • $\cap, \cup, \setminus$

... or some extension / contraction of these. These were just a random guess to start with. Ideally you could also add in $\Bbb{C}$-valued operators and so on, taking care that only $\Bbb{C}$-defined functions are called on a $\Bbb{C}$-value. But I'm just working on something simple to see if the idea works.

To represent all expressions on a computer you usually use what's called an expression tree where the nodes are operators or constants and the children of the nodes are other nodes, and so you see it recurses down until the full expression is defined.

Currently I have this explosion of an enumeration of types of operators, for instance I wanted the set operation $S\times S \to S$ to be equally represented with an integer binary operation.

#Set-valued:
setMap, setBinaryMap, setIntMap,
setOp, setBinaryOp, intToSetOp,
intToSetBinOp,
# Int-valued:
intOp, intBinaryOp, setToIntOp, 
# Terminal:
freeVariable, constInt, constSet

This variant type in Nim has led to an explosion of repetitive code. I would like to rewrite with a new representation, for instance:

  • All functions are $n$-ary operations on integers
  • The functions can return $\{\}$ (empty set)
  • For any $n$-ary set function there's an integer $n$-ary operation such that $f(A,B,C) = \{f(a,b,c) : (a,b,c) \in A\times B\times C\}$ represents the set operation.

This leads to weirdness though, like representing set union as $f(x,y) = \{x, y\}$ would lead to inefficiencies in computing the union if you were to do so without modifying the representation scheme.

So, what I'm looking for is a shorter list of types (intOp, setOp, intBinOp, etc) that is generalizable to other areas of math and also is much shorter than the list I have.

For instance again, maybe all constants and variables can be sets and when the sets are singleton we can write them as only an element when it comes time to presenting the identity formula on the screen.

Here's an example string of an expression tree output from my code:

(root: mul(gcd(y,sub(gcd(x,z),gcd(sub(42,7),24))),max(15,gcd(51,mod(add(add(10,gcd(add(96,71),38)),mod(81,44)),lcm(78,gcd(70,mul(84,sub(mul(26,69),gcd(gcd(45,77),5))))))))), free_vars: @[y, x, z])

Please advise. Thanks.

PS. I know that filtering out the algebraically trivial / useless ones will be a hard task.

$\endgroup$
0
$\begingroup$

All constants are finite sets. All variables are singleton sets of the variable: $\{v\}$. All maps are $n$-ary set maps. So in the expression tree there would be three types:

CONST SET
VAR
N-ARY MAP

For example.

There could be an operators $\text{div}$ that returns the set of divisors of all integers in its input set. And a sum operator that sums all elements of a set to a singleton, and sim. for power, so that $\sigma_k(n) $ becomes $\sum\text{pow}(\text{div}(n), \{k\})$. And if I want stronger tendency toward a certain function like $\sigma_k(n)$, then I make another set operator that defines it and put it into the operator table with possibly a higher weight.

This has the downside that each and every operator will have to be coded for sets, but this isn't a huge downside as the number of operators in the table is quite short.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.