In this essay we define a functional/operator tree and proceed to then prove a conjecture proposed by Stephen Wolfram in A New Kind of Science which stated that a binary tree with leaf nodes set to 1 with the internal nodes containing the internal binary function is able to represent all natural numbers.
f(a,b)2a⊕b+1
Definition and Examples of Functional Trees
Definition and Examples of Functional Trees
Let us say we have a binary tree with leaf nodes set to 1 and each internal node contains the same internal binary function . To evaluate a tree, we define it recursively as . Intuitively, the output from the “root node” is the output of a tree. In this essay we also define that a tree “represents” a number when its evaluation is equal to .
We write some code below in order to generate visualizations of Functional Trees (opTrees) and also the list of numbers that are generated by functional trees of leaves (opNums).
f
f(value of left subtree, value of right subtree)
n
n
We write some code below in order to generate visualizations of Functional Trees (opTrees) and also the list of numbers that are generated by functional trees of
n
Generates a list representation of the functional trees recursively using the left and right subtree such that it has leaves and an internal binary function of .
n
f
In[]:=
ClearAll[opTrees]opTrees[1,f_]={{1}};opTrees[n_,f_]:=opTrees[n,f]=Flatten[Table[Module[{leftstuff=opTrees[k,f],rightstuff=opTrees[n-k,f]},Table[{f[left[[1]],right[[1]]],{left,right}},{left,leftstuff},{right,rightstuff}]],{k,1,n-1}],2]
Creates a function which takes the lists from opTrees and outputs a visual structure of the tree.
In[]:=
ClearAll[displayTree]displayTree[{val_}]:=Tree[val,None] displayTree[{val_,{left_,right_}}]:=Tree[val,{displayTree[left],displayTree[right]}]
More efficient implementation of opTrees optimized for just finding all the numbers that can be generated by an internal binary function and leaves.
f
n
In[]:=
ClearAll[opNums]opNums[1,f_]:={1}opNums[n_,f_]:=opNums[n,f]=Flatten[Table[With[{lefts=opNums[k,f],rights=opNums[n-k,f]},f@@@Tuples[{lefts,rights}]],{k,1,n-1}]]opNums[___] := $Failed
Using the functions defined above, we now show some examples with different internal binary functions.
Displaying some trees for the Plus function:
In[]:=
displayTree/@Join[opTrees[3,Plus],opTrees[4,Plus]]Join[opNums[3,Plus],opNums[4,Plus]]
Out[]=
,
,
,
,
,
,
Out[]=
{3,3,4,4,4,4,4}
As we will touch on later, with addition as the binary operator, we essentially just have a “leaf counting” tree. This can be seen from the fact that all trees with leaves output (in this example).
n
n
Displaying some trees for the internal binary function :
f(a,b)(a+b)
2
b
In[]:=
displayTree/@Join[opTrees[3,#2^2(#1+#2)&],opTrees[4,#2^2(#1+#2)&]]Join[opNums[3,#2^2(#1+#2)&],opNums[4,#2^2(#1+#2)&]]
Out[]=
,
,
,
,
,
,
Out[]=
{12,3,1872,36,16,13,4}
Displaying some trees for the internal binary function .
f(a,b)2a⊕b+1
In[]:=
displayTree/@Join[opTrees[3,BitXor[2#1,#2]+1&],opTrees[4,BitXor[2#1,#2]+1&]]Join[opNums[3,BitXor[2#1,#2]+1&],opNums[4,BitXor[2#1,#2]+1&]]
Out[]=
,
,
,
,
,
,
Out[]=
{7,10,6,9,13,16,22}
One way to analyze how “complex” a number is the minimum number of leaves a tree needs to represent a particular number and this allows us to see how much this complexity varies throughout the natural numbers.
Finds the minimum leaves to output a number. If it outputs 0, then there does not exist a tree with leaves less than or equal to maxLeaves which outputs the number.
In[]:=
ClearAll[minLeaves]minLeaves[target_,f_,maxLeaves_:20]:=Module[{result},result=SelectFirst[Range[1,maxLeaves],MemberQ[opNums[#,f],target]&,0];result]
The code below finds the minimum number of leaves of a functional tree with internal binary function as Plus such that it outputs 13.
In[]:=
minLeaves[13,Plus,20]
Out[]=
13
Missing Values
Missing Values
As we have seen, there are functions that are able to represent all numbers, and others that have missing values (holes). It’s quite obvious to see that functions can have holes–the function that just always returns 1 is an example (or any constant for that number). We can also manipulate parity; the binary function/rule will only return even numbers and thus there will be holes for odd numbers. One interesting question about an internal binary function is whether one can predict where holes are/whether any holes even exist.
One of the difficult parts of determining missing values is the difficulty to prove whether it is. We cannot be sure whether a missing value cannot actually be represented by any tree or can be represented but it takes too much computational power to check any trees with a larger amount of leaves. The most obvious example is just the Plus function.
2(a+b)
f
One of the difficult parts of determining missing values is the difficulty to prove whether it is. We cannot be sure whether a missing value cannot actually be represented by any tree or can be represented but it takes too much computational power to check any trees with a larger amount of leaves. The most obvious example is just the Plus function.
Finds the minimum number of leaves to represent the numbers from 1–15, with the maximum amount of leaves a tree can have as 10 and an internal binary function of Plus.
In[]:=
Table[minLeaves[target,Plus,10],{target,1,15}]
Out[]=
{1,2,3,4,5,6,7,8,9,10,0,0,0,0,0}
As we can see, it seems that the function can only represent values up till 10. However, if we increase the maximum amount of leaves from to 15, we get the correct result.
10
In[]:=
Table[minLeaves[target,Plus,15],{target,1,15}]
Out[]=
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}
As we can see, every number is able to be represented, which is what we expect . We now show another example where it is not as obvious whether we have these "temporary" missing values or real missing values.
Finds the minimum number of leaves to represent the numbers from 1–15, with the maximum amount of leaves a tree can have as 17 and an internal binary function of .
a+b-2b(-a+b)
In[]:=
Table[minLeaves[target,#1+#2-2#2(-#1+#2)&,17],{target,1,15}]
Out[]=
{1,2,0,4,3,0,9,8,0,6,5,0,9,4,0}
In this example, we see that there many different holes in the list. However, due to our computational power, we cannot increase the maxLeaves parameter much higher and therefore it is much harder to determine whether a value is a hole or not. While these examples display the difficulties of determining missing values, there is a certain class of internal binary functions such that there exists a deterministic algorithm to figure out whether a value is a hole or not. This class of functions are the ones which are monotonically increasing, by which we mean that . This property allows us to determine if a value can be represented as follows. Since we know that can be represented, there exist numbers such that .
Since is monotonically increasing, . This puts a bound on the amount of numbers we need to check. If we show that all and (provided that and can be represented themselves) do not satisfy , then we have that is a missing value. We show this with the example of the internal binary function .
f(a,b)>max(a,b)
x
x
a,b
f(a,b)x
Since
f(a,b)
x>max(a,b)
a,b
1≤a<x
1≤b<x
a
b
f(a,b)x
x
f(a,b)(a+b)
2
b
Finds the minimum number of leaves (with maxLeaves as 10) needed to represent the numbers from 1–15 for the internal binary function .
f(a,b)(a+b)
2
b
In[]:=
Table[minLeaves[target,#2^2(#1+#2)&,10],{target,1,15}]
Out[]=
{1,2,3,4,5,6,7,8,9,10,0,3,4,5,6}
In the example above, it seems that the number 11 cannot be represented, however, all values less than 11 can be represented. We want to determine whether 11 is actually a hole. We first note that (a+b) is indeed monotonically increasing, so we can apply the observation we made. We can test the values and and check if any satisfy . If so, then is not actually a hole.
2
b
1≤a≤10
1≤b≤10
f(a,b)11
11
However, most of the time functions are not monotonically increasing. Thus, we need a different way to analyze the behavior of functions and see if there are any missing values. One way to see if a function has any missing values is to look at the values of the “nicest” trees. In this case, the “nice” trees are balanced trees, left-unbalanced trees, and right-unbalanced trees. We create functions for each of them below to return the values they generate.
We now give some examples of using these functions.
A Simpler Function: Plus
A Simpler Function: Plus
We now show that the function Plus can represent all values using the method above.
Generates visual representations of the trees left-unbalanced, right-unbalanced, and balanced binary trees.
Motivation for a Proof
Motivation for a Proof
Visualizations of the left-unbalanced trees and all their values in a list as well.
Visualizations of the right-unbalanced trees and all their values in a list as well.
Visualizations of the balanced trees and all their values in a list as well.
Proof
Proof
We now give some intuition as to why this proof should work.
Defines the function.
Calculates the values that the left-unbalanced tree outputs.
Nests the function four times (goes four “steps” ahead) and then subtracts the input to find the difference.
Note that the 1 on the “outside” of g(x)is now on the “inside” for g(x+1),further affirming our results.
Generates the tree which represents 2.
Generates the tree which represents 3.
Conclusion
Conclusion
Future Directions
Future Directions
Growth Rates
Growth Rates
One may wonder if we can construct a function such that it just a line at the top. As it turns out, it is also possible to construct a function such that every positive integer has exactly one tree that represents it.
References
References
Wolfram, S. (2002). A new kind of science. Wolfram Media. https://www.wolframscience.com
Acknowledgements
Acknowledgements
I would like to thank my mentor, Lyman P. Hurd, who gave me many great ideas throughout the project on what to explore, gave me tons of advice, and overall provided me invaluable support. I would also like to thank Program Director Rory Foulger, Academic Director Eryn Gillam, and Academic Director Megan Davis along with all the TAs who helped me with issues in my code and gave advice.
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
On functional trees
by Aaditya Bilakanti
Wolfram Community, STAFF PICKS, July 10, 2025
https://community.wolfram.com/groups/-/m/t/3501192
by Aaditya Bilakanti
Wolfram Community, STAFF PICKS, July 10, 2025
https://community.wolfram.com/groups/-/m/t/3501192