All elementary functions from a single binary operator

arxiv.org

821 points by pizza a day ago


SideQuark - 16 hours ago

This isn't unique, or even the least compute way to do this. For example, let f(x,y) = 1/(x-y). This too is universal. I think there's a theorem stating for any finite set of binary operators there is a single one replacing it.

write x#y for 1/(x-y).

x#0 = 1/(x-0) = 1/x, so you get reciprocals. Then (x#y)#0 = 1/((1/(x-y)) - 0) = x-y, so subtraction.

it's common problem to show in any (insert various algebraic structure here ) inverse and subtraction gives all 4 elementary ops.

I haven't checked this carefully, but this note seems to give a short proof (modulo knowing some other items...) https://dmg.tuwien.ac.at/goldstern/www/papers/notes/singlebi...

entaloneralie - a day ago

This is amazing! I love seeing FRACTRAN-shaped things on the homepage :) This reminds me of how 1-bit stacks are encoded in binary:

A stack of zeros and ones can be encoded in a single number by keeping with bit-shifting and incrementing.

    Pushing a 0 onto the stack is equivalent to doubling the number.
    Pushing a 1 is equivalent to doubling and adding 1.
    Popping is equivalent to dividing by 2, where the remainder is the number.
I use something not too far off for my daily a programming based on a similar idea:

Rejoice is a concatenative programming language in which data is encoded as multisets that compose by multiplication. Think Fractran, without the rule-searching, or Forth without a stack.

https://wiki.xxiivv.com/site/rejoice

eugene3306 - a day ago

This makes a good benchmark LLMs:

``` look at this paper: https://arxiv.org/pdf/2603.21852

now please produce 2x+y as a composition on EMLs ```

Opus(paid) - claimed that "2" is circular. Once I told it that ChatGPT have already done this, finished successfully.

ChatGPT(free) - did it from the first try.

Grok - produced estimation of the depth of the formula.

Gemini - success

Deepseek - Assumed some pre-existing knowledge on what EML is. Unable to fetch the pdf from the link, unable to consume pdf from "Attach file"

Kimi - produced long output, stopped and asked to upgrade

GLM - looks ok

lioeters - a day ago

> A calculator with just two buttons, EML and the digit 1, can compute everything a full scientific calculator does

Reminds me of the Iota combinator, one of the smallest formal systems that can be combined to produce a universal Turing machine, meaning it can express all of computation.

karpathy - 19 hours ago

All possible 36 distinct level-2 eml functions of one variable (the first 18 of them with entirely Real outputs, the other 18 with "intermediate" complex-valued components):

https://imgur.com/a/K7AoOFi

DoctorOetker - a day ago

EDIT: please change the article link to the most recent version (as of now still v2), it is currently pointing to the v1 version which misses the figures.

I'm still reading this, but if this checks out, this is one of the most significant discoveries in years.

Why use splines or polynomials or haphazardly chosen basis functions if you can just fit (gradient descent) your data or wave functions to the proper computational EML tree?

Got a multidimensional and multivariate function to model (with random samples or a full map)? Just do gradient descent and convert it to approximant EML trees.

Perform gradient descent on EML function tree "phi" so that the derivatives in the Schroedinger equation match.

But as I said, still reading, this sounds too good to be true, but I have witnessed such things before :)

testaccount28 - a day ago

derivation of -x seems wrong. we can look at the execution trace on a stack machine, but it's actually not hard to see. starting from the last node before the output, we see that the tree has the form

    eml(z, eml(x, 1))
      = e^z - ln(eml(x, 1))
      = e^z - ln(e^x)
      = e^z - x
and the claim is that, after it's expanded, z will be such that this whole thing is equal to -x. but with some algebra, this is happening only if

    e^z = 0,
and there is no complex number z that satisfies this equation. indeed if we laboriously expand the given formula for z (the left branch of the tree), we see that it goes through ln(0), and compound expressions.

x^-1 has the same problem.

both formulae work ...sort of... if we allow ln(0) = Infinity and some other moxie, such as x / Infinity = 0 for all finite x.

krick - a day ago

> using EML trees as trainable circuits ..., I demonstrate the feasibility of exact recovery of closed-form elementary functions from numerical data at shallow tree depths up to 4

That's awesome. I always wondered if there is some way to do this.

js8 - 18 hours ago

That's quite interesting.

Few ideas that come to my mind when reading this:

1. One should also add absolute value (as sqrt(x*x)?) as a desired function and from that min, max, signum in the available functions. Since the domain is complex some of them will be a bit weird, I am not sure.

2. I think, for any bijective function f(x) which, together with its inverse, is expressible using eml(), we can obtain another universal basis eml(f(x),f(y)) with the added constant f^-1(1). Interesting special case is when f=exp or f=ln. (This might also explain the EDL variant.)

3. The eml basis uses natural logarithm and exponent. It would be interesting to see if we could have a basis with function 2^x - log_2(y) and constants 1 and e (to create standard mathematical functions like exp,ln,sin...). This could be computationally more feasible to implement. As a number representation, it kinda reminds me of https://en.wikipedia.org/wiki/Elias_omega_coding.

4. I would like to see an algorithm how to find derivatives of the eml() trees. This could yield a rather clear proof why some functions do not have indefinite integrals in a symbolic form.

5. For some reason, extending the domain to complex numbers made me think about fuzzy logics with complex truth values. What would be the logarithm and exponential there? It could unify the Lukasiewicz and product logics.

simplesighman - a day ago

> For example, exp(x)=eml(x,1), ln(x)=eml(1,eml(eml(1,x),1)), and likewise for all other operations

I read the paper. Is there a table covering all other math operations translated to eml(x,y) form?

qiller - a day ago

For completeness, there is also Peirce’s arrow aka NOR operation which is functionally complete. Fun applications iirc VMProtect copy protection system has an internal VM based on NOR.

Quick google seach brings up https://github.com/pr701/nor_vm_core, which has a basic idea

CGamesPlay - a day ago

I made a fun marimo notebook to try and derive these myself. I structured each cell in order based on the diagram at the end of the paper. It uses Sympy to determine if the function is correct or not.

https://gist.github.com/CGamesPlay/9d1fd0a9a3bd432e77c075fb8...

nullwiz - 20 hours ago

I made https://github.com/nullwiz/emlvm/tree/main yesterday, for fun :^)

zonked45 - 7 hours ago

Built a JS implementation today — monogate https://explorer-taupe-five.vercel.app · npm install monogate The interesting engineering problem was negation. The paper's SI gives one construction; we independently derived a two-regime approach — tower formula for y≤0, shift formula for y>0 — that stays stable to |y|<708 in IEEE 754. We also extended to ℂ. After seeing pveierland's result in this thread (i constructible from {1} in K=75 under extended-reals convention), we investigated and documented the distinction: under strict principal-branch ln where ln(0) throws, whether {1} alone generates i remains open. Under the extended-reals convention used in the paper, their construction holds. Two different grammars, not contradictory results. 109 tests. MIT. github.com/almaguer1986/monogate

lmf4lol - a day ago

Stupid question maybe (I am no mathematician), but aren't exp and ln really primitives? Aren't they implemented in terms of +,-,/,* etc? Or do we assume that we have an infinite lookup table for all possible inputs?

evnix - a day ago

Can someone explain how is this different from lambda calculus, it seems like you can derive the same in both. I don't understand both well enough and hence the question.

jekude - a day ago

What would physical EML gates be implemented in reality?

Posts like these are the reason i check HN every day

- 21 hours ago
[deleted]
selcuka - a day ago

So, like brainf*ck (the esoteric programming language), but for maths?

notorandit - a day ago

Not sure it really compares to NAND() and the likes.

Simply because bool algebra doesn't have that many functions and all of them are very simple to implement.

A complex bool function made out of NANDs (or the likes) is little more complex than the same made out of the other operators.

Implementing even simple real functions out of eml() seems to me to add a lot of computational complexity even with both exp() and ln() implemented in hardware in O(1). I think about stuff sum(), div() and mod().

Of course, I might be badly wrong as I am not a mathematician (not even by far).

But I don't see, at the moment, the big win on this.

prvc - a day ago

This is neat, but could someone explain the significance or practical (or even theoretical) utility of it?

ks2048 - 17 hours ago

This looks interesting. I haven't looked in-detail, but my first thought is - why hasn't this been found in the past? Surely, people have been interested kind of question for awhile?

vintermann - a day ago

I'm way too unschooled to say if it's important or not, but what really excites me is the Catalan structure ("Every EML expression is a binary tree [...] isomorphic to well-studied combinatorial objects like full binary trees and Catalan objects").

So, what happens if you take say the EML expression for addition, and invert the binary tree?

rurban - 19 hours ago

I like this guy. https://th.if.uj.edu.pl/~odrzywolek/homepage/index.html

tripdout - a day ago

Interesting, but is the required combination of EML gates less complex than using other primitives?

peterlk - a day ago

Reminds me a bit of the coolest talk I ever got to see in person: https://youtu.be/FITJMJjASUs?si=Fx4hmo77A62zHqzy

It’s a derivation of the Y combinator from ruby lambdas

tgtweak - 21 hours ago

This could have some interesting hardware implications as well - it suggests that a large dedicated silicon instruction set could accelerate any mathematical algorithm provided it can be mapped to this primitive. It also suggests a compiler/translation layer should be possible as well as some novel visualization methods for functions and methods.

mmastrac - 21 hours ago

I couldn't find any information on this, but is it possible that given how nicely exponentiation and logarithms differentiate and integrate, is it possible that this operator may be useful to simplify the process of finding symbolic solutions to integrals and derivatives?

nonfamous - a day ago

How would an architecture with a highly-optimized hardware implementation of EML compare with a traditional math coprocessor?

hughw - a day ago

eml(x, y) pronounced... "email"?

boutell - 19 hours ago

Halfway through I was imagining aliens to whom this operator comes naturally and our math is weird. By the end I found out that we might be those aliens.

Aardwolf - 17 hours ago

Interesting!

One thing I wonder now: NAND is symmetric while this isn't, could something similar be found where function(x, y) = function(y, x)?

hyperhello - a day ago

> eml(x,y)=exp(x)-ln(y)

Exp and ln, isn't the operation its own inverse depending on the parameter? What a neat find.

ryanhiebert - a day ago

I’d be really interested in an analysis of tau in light of this discovery. Would tau fit more naturally here than pi, as it does in other examples?

khelavastr - a day ago

Is the the same as saying everything can be made from nand gates?

psychoslave - a day ago

Very nice, though I'm not found of the name.

What comes to my mind as an alternative which I would subjectivity finer is "axe". Think axiom or axiology.

Anyone with other suggestions? Or even remarks on this one?

drdeca - 19 hours ago

“ Elementary functions, for many students epitomized by the dreaded sine and cosine, ” dreaded?

- a day ago
[deleted]
pveierland - a day ago

Got curious to see whether SymPy could be used to evaluate the expressions, so I used Claude Code to build a quick evaluator. Numeric and symbolic results appear to agree:

    nix run github:pveierland/eml-eval
    EML Evaluator — eml(x, y) = exp(x) - ln(y)
    Based on arXiv:2603.21852v2 by A. Odrzywołek
    
    Constants
    ------------------------------------------------------------------------------
      1        K=1    d=0    got 1                    expected 1                    sym=ok   num=ok   [simplify]
      e        K=3    d=1    got 2.718281828          expected 2.718281828          sym=ok   num=ok   [simplify]
      0        K=7    d=3    got 0                    expected 0                    sym=ok   num=ok   [simplify]
      -1       K=17   d=7    got -1                   expected -1                   sym=ok   num=ok   [simplify]
      2        K=27   d=9    got 2                    expected 2                    sym=ok   num=ok   [simplify]
      -2       K=43   d=11   got -2                   expected -2                   sym=ok   num=ok   [simplify]
      1/2      K=51   d=15   got 0.5                  expected 0.5                  sym=ok   num=ok   [simplify]
      -1/2     K=67   d=17   got -0.5                 expected -0.5                 sym=ok   num=ok   [simplify]
      2/3      K=103  d=19   got 0.6666666667         expected 0.6666666667         sym=ok   num=ok   [simplify]
      -2/3     K=119  d=21   got -0.6666666667        expected -0.6666666667        sym=ok   num=ok   [simplify]
      sqrt2    K=85   d=21   got 1.414213562          expected 1.414213562          sym=ok   num=ok   [simplify]
      i        K=75   d=19   got i                    expected i                    sym=ok   num=ok   [i²=-1, simplify]
      pi       K=153  d=29   got 3.141592654          expected 3.141592654          sym=ok   num=ok   [simplify]
    
    Unary functions  (x = 7/3)
    ------------------------------------------------------------------------------
      exp(x)   K=3    d=1    got 10.3122585           expected 10.3122585           sym=ok   num=ok   [simplify]
      ln(x)    K=7    d=3    got 0.8472978604         expected 0.8472978604         sym=ok   num=ok   [simplify]
      -x       K=17   d=7    got -2.333333333         expected -2.333333333         sym=ok   num=ok   [simplify]
      1/x      K=25   d=8    got 0.4285714286         expected 0.4285714286         sym=ok   num=ok   [simplify]
      x - 1    K=11   d=4    got 1.333333333          expected 1.333333333          sym=ok   num=ok   [simplify]
      x + 1    K=27   d=9    got 3.333333333          expected 3.333333333          sym=ok   num=ok   [simplify]
      2x       K=67   d=17   got 4.666666667          expected 4.666666667          sym=ok   num=ok   [simplify]
      x/2      K=51   d=15   got 1.166666667          expected 1.166666667          sym=ok   num=ok   [simplify]
      x^2      K=41   d=10   got 5.444444444          expected 5.444444444          sym=ok   num=ok   [simplify]
      sqrt(x)  K=59   d=16   got 1.527525232          expected 1.527525232          sym=ok   num=ok   [simplify]
    
    Binary operations  (x = 7/3, y = 5/2)
    ------------------------------------------------------------------------------
      x + y    K=27   d=9    got 4.833333333          expected 4.833333333          sym=ok   num=ok   [simplify]
      x - y    K=11   d=4    got -0.1666666667        expected -0.1666666667        sym=ok   num=ok   [simplify]
      x * y    K=41   d=10   got 5.833333333          expected 5.833333333          sym=ok   num=ok   [simplify]
      x / y    K=25   d=8    got 0.9333333333         expected 0.9333333333         sym=ok   num=ok   [simplify]
      x ^ y    K=49   d=12   got 8.316526261          expected 8.316526261          sym=ok   num=ok   [simplify]
genxy - a day ago

I hope this was presented at SIGBOVIK.

theodorethomas - 19 hours ago

I wonder how this combines with Richardson's Theorem.

theanonymousone - a day ago

Zero will also be handy in definitions: `0=eml(1,eml(eml(1,1),1))`.

And i is obviously `sqrt(-1)`

rvnx - a day ago

Looks like he bruteforced all combinations of two mathematical operations no ?

- a day ago
[deleted]
zogomoox - a day ago

Could this be used to prove e+pi is transcendental?

supermdguy - a day ago

Next step is to build an analog scientific calculator with only EML gates

future_crew_fan - a day ago

there ought to be a special section on HN entitled "things that will make you feel thoroughly inadequate".

anthk - 13 hours ago

This like Subleq where you can run EForth and EForth itself self-bootstraps:

https://github.com/howerj/muxleq

PD: you don't need gforth to compile:

        cc -O2 -o muxleq muxleq.c
      
Edit muxleq.fth, add some goodies by editing these values:

             1 constant opt.multi      ( Add in large "pause" primitive )
    1 constant opt.editor     ( Add in Text Editor )
    1 constant opt.info       ( Add info printing function )
    0 constant opt.generate-c ( Generate C code )
    1 constant opt.better-see ( Replace 'see' with better version )
    1 constant opt.control    ( Add in more control structures )
    0 constant opt.allocate   ( Add in "allocate"/"free" )
    1 constant opt.float      ( Add in floating point code )
    0 constant opt.glossary   ( Add in "glossary" word )
    1 constant opt.optimize   ( Enable extra optimization )
    1 constant opt.divmod     ( Use "opDivMod" primitive )
    0 constant opt.self       ( self-interpreter [NOT WORKING] )
Here are my settings.

Then, create a new ".dec" file (subleq program)

   : ./muxleq muxleq.dec < muxleq.fth > new.dec
Now, to run EForth everytime:

     ./muxleq new.dec
add these further in muxleq.fth code to have them:

     : d. tuck dabs <# #s rot sign #> type ;
     : */ */mod nip ;
The ideal place would be just below the ': dabs ' defition.
BobbyTables2 - a day ago

How does one actually add with this?

pama - 14 hours ago

Totally gives nerd sniping vibes:

https://xkcd.com/356/

nurettin - a day ago

The problem with symbolic regression is ln(y) is undefined at 0, so you can't freely generate expressions with it. We need to guard it with something like ln(1+y*y) or ln(1+|y|) or return undefined.

measurablefunc - 17 hours ago

I guess you folks don't know about iota & jot: https://en.wikipedia.org/wiki/Iota_and_Jot

lifis - a day ago

The paper somehow seems to be missing the most interesting part, i.e. the optimal constructions of functions from eml in a readable format.

Here is my attempt. I think they should be optimal up to around 15 eml.nodrs, the latter might not be:

# 0

1=1

# 1

exp(x)=eml(x,1)

e-ln(x)=eml(1,x)

e=exp(1)

# 2

e-x=e-ln(exp(x))

# 3

0=e-e

ln(x)=e-(e-ln(x))

exp(x)-exp(y)=eml(x,exp(exp(y)))

# 4

id(x)=e-(e-x)

inf=e-ln(0)

x-ln(y)=eml(ln(x),y)

# 5

x-y=x-ln(exp(y))

-inf=e-ln(inf)

# 6

-ln(x)=eml(-inf,x)

ln(ln(x))=ln(ln(x))

# 7

-x=-ln(exp(x))

-1=-1

x^-1=exp(-ln(x))

ln(x)+ln(y)=e-((e-ln(x))-ln(y))

ln(x)-ln(y)=ln(x)-ln(y) # using x - ln(y)

# 8

xy=exp(ln(x)+ln(y))

x/y=exp(ln(x)-ln(y))

# 9

x + y = ln(exp(x))+ln(exp(y))

2 = 1+1

# 10

ipi = ln(-1)

# 13

-ipi=-ln(-1)

x^y = exp(ln(x)y)

# 16

1/2 = 2^-1

# 17

x/2 = x/2

x2 = x2

# 20

ln(sqrt(x)) = ln(x)/2

# 21

sqrt(x) = exp(ln(sqrt(x)))

# 25

sqrt(xy) = exp((ln(x)+ln(y))/2)

# 27

ln(i)=ln(sqrt(-1))

# 28

i = sqrt(-1)

-pi^2 = (ipi)(ipi)

# 31

pi^2 = (ipi)(-ipi)

# 37

exp(xi)=exp(xi)

# 44

exp(-xi)=exp(-(xi))

# 46

pi = (ipi)/i

# 90+x?

2cos(x)=exp(xi)+exp(-xi))

# 107+x?

cos(x) = (2cos(x))/2

# 118+x?

2sin(x)=(exp(x*i)-exp(-xi))/i # using exp(x)-exp(y)

# 145+x?

sin(x) = (2sin(x))/2

# 217+3x?

tan(x) = 2sin(x)/(2cos(x))

moralestapia - a day ago

Whoa, this is huge!

My dearest congrats to the author in case s/he shows around this site ^^.

noobermin - a day ago

I don't mean to shit on their interesting result, but exp or ln are not really that elementary themselves... it's still an interesting result, but there's a reason that all approximations are done using series of polynomials (taylor expansion).

zephen - a day ago

Judging by the title, I thought I would have a good laugh, like when the doctor discovered numerical integration and published a paper.

But no...

This is about continuous math, not ones and zeroes. Assuming peer review proves it out, this is outstanding.

marouane53 - 14 hours ago

[dead]

mah4k4l - a day ago

According to Gemini 3.1 Pro this would shoot the current weather forecasting power through the roof (and math processing in general):

The plan is to use this new "structurally flawless mathematical primitive" EML (this is all beyond me, was just having some fun trying to make it cook things together) in TPUs made out of logarithmic number system circuits. EML would have DAGs to help with the exponential bloat problem. Like CERN has these tiny fast "harcode models" as an inspiration. All this would be bounded by the deductive causality of Pedro Domingoses Tensor Logic and all of this would einsum like a mf. I hope it does.

Behold, The Weather Dominator!