Monday, March 25, 2013

Establishing a weak order from a partial order

Here is the partial ordering relation of the power set algebra of a set of size two:
[[1 1 1 1]
 [0 1 0 1]
 [0 0 1 1]
 [0 0 0 1]]
From this partial order we can get a weak order of the vertices [#{0} #{1 2} #{3}] based upon the upper and lower bounds. The lower bound is #{0} and the upper bound is #{3}. This produces the following weak order:
[[1 1 1 1]
 [0 1 1 1]
 [0 1 1 1]
 [0 0 0 1]]
Only weak orders themselves are equivalent to their underlying weak ordering relation. Topological sorting is related to weak ordering.

Sunday, March 17, 2013

The big omega function

The big omega function (A001222) describes the number of prime divisors of a number counted with multiplicity: 0, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 3, 1, 2, 2, 4, 1, 3, 1, 3, 2, 2, 1, 4, 2, 2, 3, 3, 1, 3, 1, 5, 2, 2, 2, 4, 1, 2, 2, 4, 1, 3, 1, 3, 3, 2, 1, 5, 2, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 4, 1, 2, 3, 6, 2, 3, 1, 3, 2, 3, 1, 5, 1, 2, 3, 3, 2, 3, 1, 5, 4, 2, 1, 4, 2, 2, 2, 4, 1, 4, 2, 3, 2, 2, 2, 6, 1, 3, 3, 4, 1, 3, 1, 4, 3, 2, 1, 5, 1, 3, 2.

The numbers zero and one do not have any prime factors. The prime numbers (A000040) have one factor, the semiprimes (A001358) have two factors, and the k-almost primes have k factors.

The big omega function tells us about the maximum number of fields of a structure of some cardinality. In practice, many structures don't use the prime factorization so they have even fewer fields then they do factors.

The number of multiplicative partitions of a number n with k factors is in the interval from p(k) to B(k) where p is the number of of additive partitions of k and B is the number of equivalence relations of size k

Saturday, March 16, 2013

Differences between primes

The differences between consecutive prime numbers are 1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 14, 4, 6, 2, 10, 2, 6, 6, 4, 6, 6, 2, 10, 2, 4, 2, 12, 12, 4, 2, 4, 6, 2, 10, 6, 6, 6, 2, 6, 4, 2, 10, 14, 4, 2, 4, 14, 6, 10, 2, 4, 6, 8, 6, 6, 4, 6, 8, 4, 8, 10, 2, 10, 2, 6, 4, 6, 8, 4, 2, 4, 12, 8, 4, 8, 4, 6, 12.

The only prime numbers that have an odd difference are the first two prime numbers two and three. Twin primes have a difference of two, cousin primes have a difference of four, and sexy primes have a difference of six.

Prime triplets have differences of either 2,4 or 4,2. Prime quadruplets have differences of 2,2,4 or 2,4,2 and prime quintuplets have differences of 2,4,2,4 or 4,2,4,2. Finally, prime sextuplets have differences 4,2,4,2,4. The twin primes conjecture states that the number of differences of 2 are infinite which is necessary for there to be an infinite number of these prime k-tuples.

Friday, March 15, 2013

Enumerating labeled binary relations

Labeled binary relations on a set of size $n$ can be enumerated using the following counting sequences:
  • All relations: $2^{n^2}$
  • Commutative relations: $2^{n^{\underline 2}}$
  • Endofunctions: $n^n$
  • Permutations: $n!$
  • Equivalence relations: $B_n$
  • Weak orders: A000670

Wednesday, March 13, 2013

Algebraic combinatorics

A set of transformations on a data structure forms a transformation monoid. Place forms are a special type of transformation monoid. Another important type of transformation monoid is a permutation group. The permutation groups arise in combinatorics as the automorphism groups of graphs and various other discrete data structures such as lists.

The set of transformation monoids can be partially ordered to form a lattice. Transformation monoids that are disjoint with respect to one another and that commute with all the operations contained in each other set are independent of one another. Each transformation monoid of the cartesian product of zero or more independent transformation monoids.

By understanding transformational independence we can begin to develop an understanding of parallelism because independent operations can be run in parallel. We can also version independent objects separately to implement fine grained versioning.

Sunday, March 10, 2013

Describing structures by transformations

The automorphism group of a data structure transformations of that data structure that do not have any effect on it. The automorphism group of a list is the set of operations that map indexes to other indexes with equal value. We can enumerate all the orbits of this automorphism group on its parent symmetric group in order to enumerate all distinct permutations of the list.

Likewise, all graphs have an automorphism group of permutations that do not effect the underlying graph. Weak orderings have an automorphism group equivalent to that of a list, equivalence relations have an automorphism group that also includes exchanges of equally sized parts, and the automorphism group of an permutation is the set of all operations that commute with it.

Periodic sequences can be described by the effect of the rest operation on the sequence and finitely differentiable functions like sine and cosine can be described by the effect of differentiation on them. In this sense, the transformations on a data structure are important in both discrete and continuous mathematics.

Saturday, March 9, 2013

The well ordering principle

The set of natural numbers $\mathbb{N}$ is well ordered which means that every subset of the natural numbers can be described by a monotone increasing enumeration. Consider for example the set of prime numbers:
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53)
We can convert any prime number back into a natural number $\mathbb{N}$. For example, 547 can be converted to 100. These enumerations are endofunctions $\mathbb{N} \to \mathbb{N}$ that are reversible but not surjective. With finite functions all reversible surjective operations are automorphisms. The square numbers are another enumeration of natural numbers:
(0 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225)
The set of all subsets of $\mathbb{N}$ under set union and set intersection forms a boolean algebra with $\mathbb{N} - S$ as the complement operation. The differences between elements of this enumeration form an integer sequence. Consider the sum of the totient function:
(0 1 2 4 6 10 12 18 22 28 32 42 46 58 64 72)
The additive differences of the sum of totients is the eulers totient function itself. In this sense, these monotone enumerations are related to integer sequences in general. We can generalize integer sequences by describing sequences of rational numbers $\mathbb{N} \to \mathbb{Q}$, however, an important difference is that the set of rational numbers $\mathbb{Q}$ is not well ordered.

Friday, March 8, 2013

Finitely differentiable functions

Functions that have a differentiation iteration type with a finite size are solutions to a simple two element homogeneous LODE with constant coefficients. The solutions to a LODE can be described by a basis which in this case can be ordered by the total ordering of rational number sequences.

The function $x^2+2x+1$ would become [1,2,1,0] for the LODE $y''''=y'''$. If we set the default value of each field in this ordered basis this vector could be reduced to [1,2,1] which is equivalent to description of this function as a polynomial. The function $e^x$ is unaffected by differentiation so it would simply be [1] for $y'=y$.

The hyperbolic trigonometric functions $cosh(x)$ and $sinh(x)$ are involutions under differentiation so they would be represented by [1/2,1/2] and [1/2,-1/2]. The trigonometric functions $sin(x)$ and $cos(x)$ have order four so they would be represented as [0,0,1,0] and [0,0,0,1].

Sunday, March 3, 2013

Enumerating structure types

Structures associate places with types. If the types of the fields of a structure are enumerated then the entire structure can be enumerated. The following elements are generated by (structure {:x (enum 0 1), :y (enum 0 1)}):
{:x 0, :y 0}, {:x 0, :y 1}, {:x 1, :y 0}, {:x 1, :y 1} 
By using slot places we can enumerate other associative collections as structures. Here is {first (enum 0 1), second (enum 0 1)}
[0 0], [0 1], [1 0], [1 1]
Sets use the contains? place system so here is all subsets of #{false, true} using {(contains? false) bool, (contains? true) bool} where bool is (enum false true):
#{}, #{false}, #{true}, #{false true}
We can also associate places with structures within a structure to enumerate grids. In general, structures are essential because they combine both enumerations and places together into one.

Saturday, March 2, 2013

The linear continuum

Discrete mathematics is founded on the integers, directed graphs and other discrete structures. On the other hand, continuous mathematics is based upon continuous structures the simplest of which is the linear continuum. The unit interval [0,1] is a linear continuum whose every element can be represented by an infinite sequence of binary digits the positions of which are natural numbers.

The infinite subsets of the natural numbers numbers cannot be enumerated because attempting to determine the equality of infinite data structures leads to the halting problem. Without an enumeration these infinite subsets cannot be described by discrete mathematics and herein lies the fundamental distinction between discrete and continuous mathematics.

The probabilities of statements form a linear continuum [0,1]. Negation is defined by $1-x$, conjunction is defined by $xy$, and disjunction is defined by by $x+y-xy$. The values of zero and one are the absolute certainties used in deductive logic but that aren't used in probabilistic logic.

In order to convert [0,1] to another interval [a,b] with finite length we can use a linear polynomial $|b-a|x+a$. With infinite intervals we can use the reciprocal function and the logarithm function to achieve the same effect. A discrete partition of the linear continuum is equivalent to a discrete probability distribution.

Friday, March 1, 2013

Iteration types of differentiation

The differentiation operation is a transformation of differentiable functions and it has different iteration types for different differentiable functions:
  • Identity: $c_1e^x$
  • Idempotent: $c_1e^x + c_2$
  • Involution: $c_1e^x + c_2e^{-x}$
All functions of a certain iteration type come from solutions to first order linear ordinary differential equations such as $y'=y$, $y''=y$, and $y''=y'$. The partial ordering of iteration types helps us to understand these differential equations. In general, polynomials, exp, sin, cos, sinh, and cosh and other similar functions all produce a finite number of differentiations.