Prime distributions

Number theory is a great source of multisets, perhaps a better source then set systems as not all finite multisets are used there. Numerous number theoretic functions correspond to multiset operations applied to the prime factorization multiset.

• $\omega(n)$ the order of the prime factorization multiset
• $\Omega(n)$ the cardinality of the prime factorization multiset
• d(n) the number of parts of the multiset
• exponent(n) the exponent of the prime factorization multiset
• prime-signature(n) the signature of the prime factorization multiset

Given any set we can produce a multiset from that set by applying a function to each of its members. If this function is irreversible, this produces a multiset whose partition is more coarse then the set that proceeded it, this is why I call this functional coarsification. This can then be transformed to a relative frequency distribution. This allows us to get a relative frequency distribution for the application of any irreversible function to a set, which is an abundant source of relative frequency distributions. For example, we can apply this to the $\omega$ function for the range from one to a thousand.

{0 0.002, 
 1 0.193, 
 2 0.507, 
 3 0.275, 
 4 0.023}

This can then be compared to the application of $\omega$ from one to a hundred thousand. One see that here the distribution tends towards three to a greater extent.

{0 2.0E-5, 
 1 0.097, 
 2 0.33758, 
 3 0.38844, 
 4 0.15855, 
 5 0.01816, 
 6 2.5E-4}

It should be readily apparent that larger numbers tend to have more prime factors. This is because the divisor ordering is a suborder of the total ordering on the natural numbers. This describes the distribution of the $\omega$ function over small ranges but the Erdos-Kac theorem of probabilistic number theory says that omega(n) is normally distributed with variance and mean $log(log(n))$. This is sometimes expressed as a Poisson distribution rather then a normal distribution because the mean and variance are both the same. This describes the rate that the number of prime factors grows at on average. Probabilistic number theory is the perfect mix of multisets and probabilities, and it demonstrates how the two are intertwined as expressed through the positive integers themselves.

In a complete set of multisets (one that is submultiset closed and finite union closed) different atoms appear as independent random variables, this means that in the set of positive integers the primes act like independent random variables. This is because the positive integers are in some sense complete, as all prime factorizations appear. If they didn't this fact from probabilistic number theory certainly wouldn't work.

Noticing that positive integers themselves are multisets we can produce relative frequency distributions from them which describe the extent to which each prime is distributed within the number. For example, given the number twelve we can produce the distribution {2 2/3, 3 1/3} which of course would be the same for 144. This is associated with the values {1/3 2/3} which describe the relative frequencies of the distribution. These frequencies add up to one, so ontologically this is called a unit partition. To explore probabilistic number theory more I described the different unit partition types of different numbers within a range and how these in turn are distributed. Here are the unit fraction partitions of the first one hundred numbers and how they are themselves distributed within that range.

{*{1/3 1/3 1/3} 0.05,
 *{2/5 3/5} 0.01, 
 *{} 0.01, 
 *{1/5 4/5} 0.02, 
 *{1/2 1/2} 0.32, 
 *{1/4 1/4 1/2} 0.03, 
 *{1/3 2/3} 0.15, 
 *{1/4 3/4} 0.05, 
 *{1/6 5/6} 0.01, 
 *{1} 0.35}

A regular number, that is to say a number with a regular multiset for its prime factorization, is also a square-free power. As we can see here the main unit fraction types described at this range are the regular distributions of order one or two. The unit fraction distribution produces a finer partition then the omega function, so the different partitions are distributed in a way corresponding to the number of distinct prime factors. An antiregular number will have a unit partition that is a set rather then simply a multiset. Rather the number is a squarefree power, antiregular, or of a certain order is determined by the prime distribution of the number. Here are some more examples of prime distributions.

• The prime distribution of 360 is {3 1/3, 2 1/2, 5 1/6} this is antiregular.
• The prime distribution of 384 is {3 1/8, 2 7/8} which is highly irregular, as one prime is far more frequent then the other.
• The prime distribution of 900 is {2 1/3, 3 1/3, 5 1/3} which is regular because this is a squarefree power.
• The prime distribution of 1260 is {7 1/6, 3 1/3, 2 1/3, 5 1/6}.

We talked about the unit partitions and the $\omega$ function dealing with the distinct primes, but the different prime distributions themselves are distributed within the natural numbers in a certain fashion. This isn't too hard to find out, since each prime distribution can be expressed as an exponential equation $b^n$ for some base $b$ which has coprime multiplicities of prime factors, or in other words which is of exponent one. The counting function is therefore logarithmic, and the probability can be computed relatively from that. \[ \frac{log(n)}{log(b)*n} \] This grows asymptotically at degree negative one, which means that individual prime distributions rarely occur (as can also be inferred by their logarithmic counting function). There are an infinite number of prime distributions distributed within the positive integers, but each of them occurring relatively rarely but infinitely nonetheless.

Notice that the natural numbers can be represented as multisets of a single element, which means that the total ordering of natural numbers is simply the inclusion relation on them, then the divisibility relation is simply the relation of even divisibility of these multisets. Next, we can introduce the concept of even disibility of the prime factorization multiset instead. Another way of expressing this is that there exists a positive integer $n$ such that $a^n = b$. In this partial order, the connected components are the numbers with the same prime distributions, as only numbers with the same prime distributions can be exponentiated to get one another. This only occurs when the exponent of two numbers with the same prime distribution divide one another. This generalizes divisibilty ordering associated with multiplication to an ordering associated with exponentation. Each of these partial orders is a suborder of one another.

Relative frequency distributions of multisets

Let $A$ be a multiset. Then we can add $A$ to itself repeatedly to get $A+A$, $A+A+A$, and so on. The multisets {x,x,y},{x,x,x,x,y,y}, and {x,x,x,x,x,x,y,y,y} for example are all produced by repeatedly adding some multiset together. This means that they are equivalent to scale. The multisets {a,b,c,d,d} and {a,a,b,b,c,c,d,d,d,d} are also equivalent to scale for the same reason. This produces an equivalence relation of multisets. We can use the concept of relative frequencies to characterize this equivalence relation of multisets.

Definition: the relative frequency of some element of the support of a multiset is equal to $m/n$ where $m$ is equal to the multiplicity of the element and $n$ is equal to the cardinality of the multiset. The relative frequency distribution is the support set of the multiset with each element with each element weighted by its relative frequencies.

Definition: the exponent of a multiset is equal to the greatest common divisor of its set of multiplicities.

Using the concept of relative frequencies so defined, we can see that the relative frequency distribution of the first class of multisets is {x 2/3, y 1/3} and the relative frequency distribution of the second class of multisets is {a 1/5, b 1/5, c 1/5, d 2/5}. Multisets with a given distribution can be scaled in an infinite number of ways to get different multisets. These different multisets all belong to the same equivalence class. The multiset exponent describes the scale of the multiset.

Theorem: the product function from a multiset to the pair (relative frequency distribution, exponent) is reversible.

Proof: suppose that we have a pair (relative frequency distribution, exponent) then we can construct the corresponding multiset by scaling each relative frequency of the multiset by $lcm(D)*n$ where $D$ is the set of denominators of the relative frequency distribution and $n$ is the exponent. To see this consider first what happens when we scale the relative frequency distribution by $lcm(D)$. What we want to show is that this produces a coprime multiset, that is a multiset with exponent one.

Firstly, in order for the resulting set of multiplicities to be integers they must be multiplied by a common divisor of the set of denominators of the relative frequency distribution. If they are not then there is some element in the denominator that will not be multiplied by a value that is a multiple of it, so the resulting multiset will not consist of integers. But the least common multiple (LCM), is the smallest common multiple of the integers in the divisibility lattice which means the gcd of the resulting multiplicities will be one because if it wasn't then it wouldn't be the least common multiple but rather a greater common multiple. To then get the proper multiset scale that further by the multiset exponent in the second part of the pair so that the gcd is $n$.

This product function isn't only one to one it is a complete destructuring of multisets because the equivalence class of multisets up to scale and the equivalence class of multisets with the same exponent are both independent of one another in the lattice of equivalence relations related by coarsification and refinement. This makes it especially valuable type of reversible function.

Postulate: the regularity, antiregularity, and the order of a multiset are determined by its relative frequency distribution

Actually, these are all determined by the support partition of the multiset which is the partition of the support of the multiset by equivalent multiplicites. Two relative frequencies of a given multiset are only equal if their corresponding multiplicities are because $m_1/n = m_2/n$ can be simplified by multiplying both sides by $n$ to get $m_1=m_2$ so all the properties of the support partition are preserved by the relative frequency distribution. Regular multisets produce regular distributions and antiregular multisets produce antiregular distributions.

Classification of set systems by degree multisets

In set theory in a multiset theoretic context the key role of multisets in the theory of set systems in set theory was explained. In particular, a multiset can be formed from a set system by adding all the sets of the set system together counting repetition, which determines the degree distribution of the set system. This is a brief overall survey of the different properties of set systems determined by the degree multiset.

Cardinality sum
The cardinality sum of the set system is equal to the sum of the cardinalities of the sets of the set system, and it corresponds to the cardinality of the multiset. The cardinality sum is the best measure of the size of a set system. Cardinality one multisets include {x}, cardinality two ones include {x,x},{x,y}, and so on. Cardinality sum one set systems are rank one chain families, cardinality sum two set systems are max order two independent families, and cardinality three set systems are either max order three set systems or they are ordered pair like set systems such as the kuratowski pair {{0},{0,1}}. A full survey is presented in set systems of small size .

Order
The order of a set system is the cardinality of its union, and the order of a multiset is the cardinality of its support. Set systems with bounded order have a bounded cardinality sum up to $2^n$ where $n$ is the order, and set systems with bounded cardinality sum are bounded by the same order. This means there are more set systems of a given order, so the kuratowski pair and ordered pairs are order two and so is the larger cardinality sum set system {{0},{1},{0,1}} which is power set like.

Regular families
Regular families are families for which the degree of each element is the same, and they correspond to regular multisets like {a,b,c},{a,a,b,b,c,c}, {a,a,a,b,b,b,c,c,c}, {a,a,a,a,b,b,b,b,c,c,c,c,d,d,d,d}. Corresponding regular families include {{a},{b},{c}}, {{a,b},{a,c},{b,c}}, {{a,b},{a,c},{b,c},{a,b,c}}, and {{a},{b},{c},{d},{a,b},{a,c},{b,c},{a,b,c}}. Finite power set like set systems are a special case of regular families determined by the condition that the cardinality sum is $2^n$ which is the highest it can be for the order of the set system.

Antiregular families
Antiregular families are families for which the degree of each element is different, and they correspond to antiregular multisets like {a},{a,b,b},{a,b,b,c,c,c}, and {a,b,b,c,c,c,d,d,d,d}. Actually, the antiregular multisets must all take this form as multisets like {a,b,b,b} have no corresponding set system partition so they are actually called progression multisets as their multiplicities form a range over the natural numbers. Ordered pairs can be determined by their degrees multiset which is the basis of the multiset theoretic definition of the ordered pair.

Maximum and minimum degrees
Independent families are set systems for which the intersection of all sets is empty, they are also determined by their degree multisets, as their degree multisets are actually sets. Consider the independent family {{0,1},{2,3}} its combinational sum is {0,1,2,3} which is a set, and in this case multiset addition is equal to the union. Max degree two, max degree three, and max degree four families are generalizations. Powerful families are set systems for which each union member has degree at least two. These properties are determined from the minimum and maximum multiplicity of the degrees multiset.

Repetitiveness and pseudo-independent families
The repetitiveness of a multiset is the extent to which it is not a set, or the cardinality of the multiset minus the cardinality of the support. This means that for a set system, it is equal to the cardinality sum minus the order. It is maximized for power sets and minimized for independent families. It is also equal to the total intersection size of the set system, which is the total number of times sets intersect. Every set system has a fundamental intersection multigraph associated with it, which is a multigraph rather then an ordinary graph because sets can have more then one value in common between them.

Antiregular families

Set systems can be classified by their degree multisets. Regular families are the set systems in which the degree of each union member is equal, antiregular families by contrast are the set systems for which the degree of every union member is different. Progression families like {{0} {0 1} {0 1 2} {0 1 2 3}} are antiregular because the degree of each union member is different from the others. Kuratowski pairs, rather they are equal like {{0}} or distinct like {{0} {0 1}} are also antiregular.



Antiregular families characterize the total orderings on a set (all preorders and graphs can be described as set systems), but not the total preorderings because preorders can have elements that are equal and indistinguishable. The total ordering on the set can be recovered from the multiset alone by the ordering of the multiplicities of the multiset, which is the basis of the multiset theoretic definition of the ordered pair. The corresponding progression family then be recovered from the multiset by the total ordering, which means antiregular families a special case of family that can be recovered directly from their multisets.

The same properties don't occur for sets of multisets, as sets of multisets can take a variety of forms besides progressions for example like {{0}, {1,1}}. Progressions of multisets which can be used to characterize sequences in pure multiset theory aren't always antiregular like with {{0},{0,1},{0,1,1}} which is equal to (0 1 1). This is actually a regular progression of multisets rather then an antiregular one which shows that this property of recoverability from the multiset does not apply sets of multisets like it does to sets of sets.

Regular families

Regular families are families for which every member of the union of the sets of the family has the same degree. They are a special case of the classification of set systems by their degree multisets (the ontology of multisets determines the classification by degrees). So a regular multiset by comparison is a multiset in which the multiplicity of each element is equal for example {a,a,a,b,b,b,c,c,c} is regular because the multiplicity of each element is equal. The ontology of regular families is included below.



Special cases include the rank complete families, which are set systems determined by the collection of all subsets of some set, typically produced with the selections function and the union of such sets. Another special case is the case of independent families (families whose degree multisets are actually sets which works because sets are regular multisets) which is a different classification by degrees. Similar concepts of regular families emerge from the set theoretic representation of the graphs (either maximal cliques families or dependency families).

Approaches to artificial intelligence

The good old fashioned approach to artificial intelligence (AI) is based ontology engineering and knowledge base construction. The earliest ontology languages like KIF were dialects dialects of Lisp because of its association with the artificial intelligence community. Ontology languages used today are now more often based upon XML like OWL. Given some domain, all the semantic relations between objects in that domain can be specified to create a semantic network.

The main alternative trend in artificial intelligence right now is to use neural networks. Neural networks have gained a lot more traction under the name deep learning. It is well known that neural networks have surpassed humans at go playing. Combinatorial game theory is essentially a solved problem as humans are generally going to have a hard time against a well trained neural network.

I have great optimism in the future of semantic networks, the modeling of semantic relationships between phenomena can still be greatly improved. In particular, semantic networks are especially useful for modeling symbolic thought. I think even as neural networks are improved semantic networks and ontology engineering are still worth pursuing and can still be improved on their own. Perhaps superhuman artificial general intelligence will be created with some appropriate combination of semantic networks, neural networks, and other methods.

See also: Symbolic vs Connectionist A.I.