Featured Post

Today is Pi approximation day (22/7) and I will use that as an excuse to share my new favourite expression for Pi:

 

And this isn't even an approximation! Recently, continuous mathematics has found its own equivalent to the digital hardware NAND gate. In his paper “All elementary functions from a single binary operator”, Andrzej Odrzywołek demonstrated that a single functional primitive can generate the entire standard continuous spectrum of operations. In other words, every single button on a scientific calculator, from addition and subtraction to sines, cosines, and logarithms, can be built using just this one function.

This Maple Worksheet explores how the 'Exp-Minus-Log' ("EML") operator, when paired solely with the constant 1, can be systematically nested to construct basic arithmetic, constants, and complex transcendental functions within Maple.

In essence, he discovered that the binary operator EML, along with the constant 1, forms a basis for the set of standard scientific-calculator operations.

This means that functions like sin(x)cos(x) and operations like a-b or a^b can be creating by composing EML with itself in clever ways. Some constants and functions are trivial to represent, such as EML(1,1) = e or EML(x, 1) = exp(x), others however, are not...

With a quick one-command tweak, you can get Maple to use the property of the extended reals that

And then with a simple argument about standard branches, you can construct the natural logarithm for real numbers, which immediately leads the constant zero:

 

You can then expand the tools in your toolbox by creating subtraction with EML, ln(x), and exp(x)

Which then expands the toolbox further by allowing for the construction unary minus from the constant 0 (since -x = 0 - x), and then addition (since a+b=a-(-b))

Since we've constructed addition, subtraction, zero and one, we can technically construct every integer! It would not be very pleasant, and by no means optimal... but you could! Here's 7 for example:

The next step to building all the standard functions is multiplication and inversion. And these use the classic trick by using the fact that x=exp(ln(x)) can help simplify:

These are compositions of exp, addition, ln, and unary minus (all functions constructed previously), which means they can be made with only EML:

 

It's at this point that I will leave the derivation of division (a/b) and exponentiation (a^b) as exercises for the reader, so I can skip to something a little more complex...

To go beyond the basic operators, you'll need to step into the complex domain by constructing the imaginary constant i. To do this, take ln(-1) = -i*Pi (by using the standard branch) and combine it with Euler's formula

And once again the expression on the left-hand side is made up of operations that were all previously defined, so you can compose EML to get a new constant:

And finally, it's possible to break down the expression for Pi from the start, since it's the product i*ln(-1)

 

By successfully extracting the mathematical constants i and Pi, I think this demonstrates the complete constructive capability of the EML operator in the complex domain. While the resulting syntax trees become exponentially deep and unoptimized for human readability, they prove that continuous operations do not require a massive, distinct toolbox. Future applications of this uniform binary structure could dramatically simplify symbolic regression and machine learning optimization models. 
Ultimately, the EML operator reveals the remarkable truth that the vast complexity of scientific mathematics can be distilled down to a single, beautiful building block.


Isn't math awesome?

Featured Post

9404

The Miracle of Integer Eigenvalues is a paper that shows how any partially-ordered set can be used to generate a matrix with integer eigenvalues.

R. Kenyon et al, Funct. Anal. Its Appl. 58, 182–194 (2024)  doi: 10.1134/S0016266324020072, arXiv:2401.05291v2

Here I outline the process and give two examples.

restart

PartiallyOrderedSets is after GraphTheory so its DrawGraph gets priority.

with(GraphTheory); with(LinearAlgebra); with(PartiallyOrderedSets)

Example (the first example in the paper): Poset in 3 elements with one relation {u < v, {u, v, w}}.

vars := [u, v, w]; n := nops(vars); rels := {u < v}

[u, v, w]

3

{u < v}

Some derived things we will need.

translate := `~`[`=`](vars, [`$`(1 .. n)]); arcs := map(`@`(`[]`, op), rels); A := AdjacencyMatrix(Graph(vars, arcs))

translate := [u = 1, v = 2, w = 3]

arcs := {[u, v]}

Matrix(%id = 36893490746138016812)

p := PartiallyOrderedSet(vars, A)

module PosetObject () local numElems::':-integer', height::':-integer', width::':-integer', comparator::procedure, comparatorExists::boolean, transitiveClosure::Matrix, transitiveClosureExists::boolean, transitiveReduction::Matrix, transitiveReductionExists::boolean, elementMap::table, minimalElements::set, minimalElementsExists::boolean, leastElement::':-integer', maximalElements::set, maximalElementsExists::boolean, greatestElement::':-integer', closureGraph::Graph, closureGraphExists::boolean, connectedComponents::(set(set)), connectedComponentsExists::boolean, reductionGraph::Graph, reductionGraphExists::boolean, adjList::Array, adjListExists::boolean, isLattice::boolean, isFaceLattice::boolean, grade::':-integer', isGraded::boolean, isRanked::boolean, rankFuction::procedure, rankTable::Array, rankFuctionExists::boolean; option object; end module

We can represent this as a directed graph.

DrawGraph(p, size = [200, 200])

There are three linear extensions; roughly these are linear orders/chains with all of {u, v, w} that maintain u < v. In this case there are three: u < v and v < w, u < w and w < v, w < u and u < v. In other words, we want to find all permutations of [1,2,3] in which 1 (=u) precedes 2 (=v). We can use the iterator TopologicalSorts, which finds all permutations satisfying some relations.

T := Iterator:-TopologicalSorts(n, subs(translate, rels))

_m2598758943744

The three permutations that have u before v are given below both numerically and symbolically.

extnums := [seq([seq(t)], `in`(t, T))]; exts := [seq(vars[[seq(t)]], `in`(t, T))]

[[1, 2, 3], [1, 3, 2], [3, 1, 2]]

[[u, v, w], [u, w, v], [w, u, v]]

Choose two of these, P and Q, say the first two.

Pnum, Qnum := extnums[1 .. 2][]; P, Q := exts[1 .. 2][]

[1, 2, 3], [1, 3, 2]

[u, v, w], [u, w, v]

Then the kth node in Q is a (P,Q) disagreement node or descent node if the k-1th node in Q is greater than the kth node, considered as a relation in P.  For example, for k = 2 (w in Q), so k-1 = 1 (u in Q) then in P we have u < w and w is a (P,Q) agreement node. For k = 3 (v) and k-1 = 2 (w) we have w > v in P and disagreement. The first node in Q is defined to be an agreement node. So u = agree, w = agree, v = disagree. We make a list of agreements (0) and disagreements (1) from k = 2 to k = n and find [0,1].

As a procedure we have

eps := proc(P::permlist, Q::permlist)
local k, i, j, L;
for k from 2 to nops(Q) do
  member(Q[k-1], P, 'i');
  member(Q[k], P, 'j');
  if i < j then L[k] := 0 else L[k] := 1 end if;
end do;
convert(L, list);
end proc:

eps(Pnum, Qnum)

[0, 1]

So now we do this for all P,Q pairs and fill a 3x3 matrix with a variable indexed with the generated lists

M := Matrix(nops(extnums), proc (i, j) options operator, arrow; index(a, eps(extnums[i], extnums[j])[]) end proc)

:=

And we find this matrix has eigenvalues that are linear combinations of these variables, with integer coefficients

Eigenvalues(M, output = list)

[a[0, 0]-a[1, 0], a[0, 0]-a[0, 1], a[0, 0]+a[1, 0]+a[0, 1]]

And of course if these variables had integer values, the matrix would have all integer eigenvalues.

inds := indets(M); r := rand(-20 .. 20); M2 := eval(M, `~`[`=`](inds, {seq(r(), 1 .. nops(inds))})); Eigenvalues(M2, output = list)

M2 :=

[7, -7, -6]

Example 2: A poset with the Hasse diagram: (generated below)

It is convenient to enter only the arcs shown (not b<e)

vars := [a, b, c, d, e]; n := nops(vars); rels := {a < c, b < c, b < d, d < e}

[a, b, c, d, e]

5

{a < c, b < c, b < d, d < e}

Specify input = transitivereduction so the missing relation doesn't throw an error.

translate := `~`[`=`](vars, [`$`(1 .. n)]); arcs := map(`@`(`[]`, op), rels); A := AdjacencyMatrix(Graph(vars, arcs)); p := PartiallyOrderedSet(vars, A, input = transitivereduction)

translate := [a = 1, b = 2, c = 3, d = 4, e = 5]

arcs := {[a, c], [b, c], [b, d], [d, e]}

Matrix(%id = 36893490746159485164)

module PosetObject () local numElems::':-integer', height::':-integer', width::':-integer', comparator::procedure, comparatorExists::boolean, transitiveClosure::Matrix, transitiveClosureExists::boolean, transitiveReduction::Matrix, transitiveReductionExists::boolean, elementMap::table, minimalElements::set, minimalElementsExists::boolean, leastElement::':-integer', maximalElements::set, maximalElementsExists::boolean, greatestElement::':-integer', closureGraph::Graph, closureGraphExists::boolean, connectedComponents::(set(set)), connectedComponentsExists::boolean, reductionGraph::Graph, reductionGraphExists::boolean, adjList::Array, adjListExists::boolean, isLattice::boolean, isFaceLattice::boolean, grade::':-integer', isGraded::boolean, isRanked::boolean, rankFuction::procedure, rankTable::Array, rankFuctionExists::boolean; option object; end module

The graph is the transitive reduction (Hasse diagram).

DrawGraph(p, size = [200, 200])

Update the relations to include all those in the transitive closure (including b<e)

Edges(ToGraph(p, reduction = false)); rels := map(`@`(`<`, op), %)

{[a, c], [b, c], [b, d], [b, e], [d, e]}

{a < c, b < c, b < d, b < e, d < e}

Find the 9 linear extensions

T := Iterator:-TopologicalSorts(n, subs(translate, rels)); extnums := [seq([seq(t)], `in`(t, T))]; exts := [seq(vars[[seq(t)]], `in`(t, T))]

_m2598743159552

[[1, 2, 3, 4, 5], [1, 2, 4, 3, 5], [1, 2, 4, 5, 3], [2, 1, 3, 4, 5], [2, 1, 4, 3, 5], [2, 1, 4, 5, 3], [2, 4, 1, 3, 5], [2, 4, 1, 5, 3], [2, 4, 5, 1, 3]]

[[a, b, c, d, e], [a, b, d, c, e], [a, b, d, e, c], [b, a, c, d, e], [b, a, d, c, e], [b, a, d, e, c], [b, d, a, c, e], [b, d, a, e, c], [b, d, e, a, c]]

Leading to the matrix

M := Matrix(nops(extnums), proc (i, j) options operator, arrow; index(a, eps(extnums[i], extnums[j])[]) end proc)

Matrix(%id = 36893490746138048980)

The eigenvalues

Eigenvalues(M, output = list)

[a[0, 0, 0, 0]-a[0, 0, 1, 0], a[0, 0, 0, 0]-a[0, 0, 1, 0]-a[1, 0, 0, 0]+a[1, 0, 1, 0], a[0, 0, 0, 0]-a[0, 0, 1, 0]+a[1, 0, 0, 0]-a[1, 0, 1, 0], a[0, 0, 0, 0]-a[0, 0, 0, 1]-a[1, 0, 0, 0]+a[1, 0, 0, 1], a[0, 0, 0, 0]-a[0, 0, 0, 1]-a[0, 1, 0, 0]+a[0, 1, 0, 1], a[0, 0, 0, 0]+a[0, 0, 0, 1]-a[0, 1, 0, 0]-a[0, 1, 0, 1], a[0, 0, 0, 0]-a[0, 0, 0, 1]+a[0, 1, 0, 0]-a[0, 1, 0, 1]+a[1, 0, 0, 0]-a[1, 0, 0, 1], a[0, 0, 0, 0]+a[0, 0, 0, 1]+a[0, 0, 1, 0]-a[1, 0, 0, 0]-a[1, 0, 0, 1]-a[1, 0, 1, 0], a[0, 0, 0, 0]+a[0, 0, 0, 1]+2*a[0, 0, 1, 0]+a[0, 1, 0, 0]+a[0, 1, 0, 1]+a[1, 0, 0, 0]+a[1, 0, 0, 1]+a[1, 0, 1, 0]]

and with some integer entries

inds := indets(M); M2 := eval(M, `~`[`=`](inds, {seq(r(), 1 .. nops(inds))})); Eigenvalues(M2, output = list)

M2 :=

[0, -68, -32, 3, -12, 8, -8, -6, -2]

NULL

IntegerEigenvalues.mw

 



Permutation.

asked by Christian... 1680 Yesterday