Tuesday, October 30, 2018

Prefix sublist ordering

Given a set of sequences or lists, we can partially order them by rather or not one list can be embedded in another from the start. This produces a partial ordering of the set of sequences or lists we are being given.

This partial ordering is necessarily going to be a lower forest for any given relation, but if it as a prefix sublist closed relation then it is going to be a lower tree like the one shown above. One example where this prefix sublist ordering may be used is to order the sequences of indices or keys of some data structure. If that data structure is a nested list, then its sequences of integer indices can also be ordered by the lexicographic ordering. The following routine demonstrates the lexicographic ordering. Its relatively easy to implement, the main thing is to order the check the order of the first indices of the sequences and then recursively check the rest of the indices.
(defn lexicographic-successor?
  [a b]

  (cond
    (empty? a) true
    (empty? b) false
    :else (and
           (<= (first a) (first b))
           (lexicographic-successor? (rest a) (rest b)))))

This lexicographic ordering of the sequences of indices which are themselves ordered as a tree by the prefix sublist ordering produces an ordered tree. Such ordered trees are counted by the Catalan numbers $C_n$. As they are ordered trees they correspond to pure lists. The build-pure-list routine can produce a pure nested list from a such a set of indices and the get-indices routine can be used to convert any list rather it is pure or not into a set of indices.
(defn get-indices
  [coll]

  (if (empty? coll)
    #{(list)}
    (set
     (cons
      (list)
      (mapcat
       (fn [i]
         (let [v (nth coll i)]
           (if (and (seq? v) (not (empty? v)))
             (map (partial cons i) (get-indices v))
             (list (list i)))))
       (range (count coll)))))))

(defn build-pure-list
  [indices]

  (let [current-coll (sort
                      <
                      (apply
                       union
                       (map
                        set
                        (filter
                         (fn [i] (= (count i) 1))
                         indices))))]
    (map
     (fn [i]
       (build-pure-list
        (for [index indices
              :when (= (first index) i)]
          (rest index))))
     current-coll)))

It was already stated that the prefix sublist ordering is a lower tree. This means that is a meet semilattice (it is only missing a maximal element). As a result, we can compute the meet of two different elements using the longest-common-prefix function.
(defn longest-common-prefix
  [a b]

  (if (or (empty? a)
          (empty? b)
          (not= (first a) (first b)))
    '()
    (cons (first a) (longest-common-prefix (rest a) (rest b)))))

Making use of this longest-common-prefix routine, we can compute the distance between two elements in the tree. The distance is the sum of the distances to their longest common prefix, which being a prefix is only equal to the difference of their sizes. Then making use of the lexicographic ordering provided by lexicographic-predecessor as well as the
(defn indices-distance
  [a b]

  (let [ancestor (longest-common-prefix a b)]
    (+ (Math/abs (- (count ancestor) (count a)))
       (Math/abs (- (count ancestor) (count b))))))

(defn indices-distances
  [coll]

  (let [sorted-coll (sort lexicographic-successor? coll)]
    (map
     (fn [i]
       (indices-distance
        (nth sorted-coll i)
        (nth sorted-coll (dec i))))
     (range 1 (count sorted-coll)))))

This produces a sequence of positive integers corresponding to the distances of the tree. These sequences of distances fully determine the structure of the ordered tree. Given a monotone sequence, we can compute a sequence of distances from that monotone sequence sequence by taking the differences between elements of the sequence and adding one to make them positive. Further, given a semiorder we can compute such a monotone sequence from the cardinality of the sets of predecessors of each of its elements which fully determines the semiorder. That monotone sequence can then be converted into a sequence of distances and then into an ordered tree. This demonstrates the correspondence between these two types of Catalan structures, the ordered trees and semiorders.

Friday, October 26, 2018

Lattice completions

Given a partial ordering relation there are three types of elements that can occur in it defined below.
  • Minimal element : an element with no predecessors
  • Maximal element : an element with no successors
  • Enclosed element : an element which is neither minimal nor maximal
Any partial ordering relation can be extended to form a lattice, by adding certain elements to it. These elements are going to be either minimal, maximal, or enclosed. Here is an example of a lattice completion that demonstrates each type of element, highlighted in blue added to a partial order:

A lattice, therefore, is in some sense a special type of partial order that has certain elements added to it. The dissimilarity or the distance of a given partial order to a lattice is the number of elements that need to be added to it in order to get a lattice. It is worth considering certain classes of partial orders that have bounded dissimilarity to a lattice.
  • Difference zero : these are elements that are already lattices themselves
  • Difference one : meet semilattices are missing only a maximal element, join semilattices are missing only a minimal element, and partial orders that are missing only an enclosed element
  • Difference two : unique extrema partial orders that are missing only minimal and maximal elements but not any enclosed elements
The unique extrema partial orders which are missing only extremal elements and which are not missing any enclosed elements seem to be an interesting particular case. They are at most distance two from a lattice, and they include semilattices which are at most distance one, and lattices themselves as special cases.

The strongly unique extrema partial orders are a special case of unique extrema partial orders, which are closed under taking suborders. Forests are a special case of strongly unique extrema partial orders, and trees are a special case that are also semilattices. Locally total orders are a special case of forests that are both upper forests and lower forests. Total orders are a special class of locally total orders. All of these classes of partial orders are at most distance two from a lattice, making them relatively similar to lattices. Other classes can be distinguished by their similarity to lattices.

Wednesday, October 24, 2018

Boolean formulas as lattice polynomials

Given any lattice ordered set, we can form lattice polynomials from the use of variables like x,y,z and so on as well as the lattice operations $\wedge$ and $\vee$. On two elements we have lattice polynomials like $$a \wedge b$$ $$a \vee b$$ Which shows that in general, on two elements the types of lattice polynomials that we can form on them are not that interesting. On three elements we can form a wide variety of lattice polynomials like $$a \vee (b \wedge (c \vee d))$$ $$a \wedge (b \vee (c \wedge d))$$ In general, for any given lattice, these lattice polynomials can be arbitrary trees that can be expanded to any given depth. In a distributive lattice, on the other hand, the lattice polynomials can be reduced to only two elements which can be expressed one of two ways, either as the meet normal form or as the join normal form of their variables. $$ (a \vee b \vee c) \wedge (d \vee e \vee f) \wedge (g \vee h \vee i) $$ $$ (a \wedge b \wedge c) \vee (d \wedge e \wedge f) \vee (g \wedge h \wedge i)$$ A boolean algebra is a special case of a lattice, therefore boolean formulas can be expressed as a special case of lattice polynomials, with the only adjustment being that variables can be either negated or not. Boolean algebras are distributive, therefore every boolean formula can be expressed as either the conjunctive normal form or the disjunctive normal form. This shows that propositional logic deals with a subset of lattice theory.

Combinatorial use of the Catalan numbers

The Catalan numbers count a number of structures that appear in mathematics like ordered trees, monotone paths, non-crossing partitions, unlabeled semiorders, etc. But one of the most interesting things about Catalan numbers is that they count the number of expressions that can be built from purely parenthesis like these.
()
(())
(() ()), ((()))
(() () ()), (() (())), ((()) ()), ((() ())), (((())))
In other words, these Catalan numbers can be used to count the number of Lisp expressions built purely from the parenthesis. For those of us interested in list processing, it is worth considering the Catalan numbers and the structures related to them.

Friday, October 19, 2018

Asymptotic growth of the Catalan numbers

The Catalan numbers have a convenient definition in terms of the central binomial coefficient, which is defined by the factorial. As such, we can compute the asymptotic growth of the Catalan numbers using the asymptotic definition of the factorial we already have acquired using Stirling's formula. The central binomial coefficient is equal to $2n$ factorial divided by $n$ factorial squared. $$\frac{(2n)!}{{(n!)}^2}$$ We can plug in the asymptotic definition of the factorial into the above equation to get the following formula. $$\frac{ \frac{\sqrt{2\pi (2n)} (2n)^{2n}}{e^{2n}} }{ (\frac{\sqrt{2\pi n} n^n}{e^n})^2 } $$ In order to reduce this formula first we will notice that the $e^{2n}$ on both sides of the equation can be eliminated. To simplify the denominator notice that the square root of four is two, which can be pulled out of the square root. Then simplify $(2n)^{2n}$ by pulling out each of its factors. Then to simplify the denominator square it by multiplying the exponent of the factors by two, eliminating the square root. This results in the following reduced formula $$\frac{ 2(\sqrt{\pi n}) 4^n n^{2n} }{ 2(\pi n) n^{2n} } $$ It is plainly apparent that $2$ and $n^{2n}$ can be eliminated from both sides of the ratio. Then the two terms involving $\pi n$ can be simplified by adding their exponents which effectively puts the square root in the denominator. $$\frac{4^n}{\sqrt{\pi n}}$$ This is the asymptotic definition of the central binomial coefficient. Then in order to get the asymptotic growth of the Catalan numbers from this all that we have to do is divide it by $n+1$. $$C_n \sim \frac{4^n}{\sqrt{\pi n}(n+1)}$$ This gets us the asymptotic definition of the Catalan numbers. They grow at the rate of an exponential function with a base of four. This demonstrates that the asymptotic definition of the Catalan numbers can be acquired just from the definition of the asymptotic growth of the factorial which we have already shown.

Thursday, October 18, 2018

Stirlings approximation

The factorial is typically defined by the product of the first $n$ numbers. It can therefore be assumed that the factorial can simply be defined by the product of the first $n$ numbers and that is all there is to it. But actually, to compute the factorials of large numbers it is better to use a different algorithm then that. The best ones tend to use the prime factorization, by noting that the prime factors of $n!$ are all less then $n$ as well as some variant of Legendre's formula which determines the exponents of the prime factors of the factorial. The best algorithm to compute factorials seems to be the prime swing algorithm which reduces it to the swings, with a good big integer library this can be used to compute very large factorials quickly.

Considering that the factorial can be expressed in different ways, it is worth considering how it can be expressed asymptotically. To begin with we know that the factorial function $n!$ grows super-exponentially because $n!$ is multiplied by increasing large numbers as the sequence grows. When one considers super-exponential functions one of the first functions that comes to mind is $n^n$. As it turns out the ratio between $n^n$ and $n!$ grows only exponentially, so it can be reduced. In order to consider the base of this exponential growth rate, we will divided consecutive terms of it. $$\frac{\frac{(n+1)^{(n+1)}}{(n+1)!}}{\frac{n^n}{n!}}$$ We can change $(n+1)!$ to $n!*(n+1)$ and then remove $n!$ from both sides. After that we can remove one from the exponent of $n+1$ by dividing it by $n+1$ to get the reduced formula. $$\frac{(n+1)^n}{n^n}$$ The resulting formula ${(\frac{n+1}{n})}^n$ is precisely the limit definition of $e$ which is what we are familiar with. $${(\frac{n+1}{n})}^n$$ This demonstrates that the ratio between $n^n$ and $n!$ grows exponentially. As both of these two functions have interpretations in combinatorics, with $n^n$ counting the number of functions on a set and $n!$ counting the number of them that are reversible, this counts the ratio of reversibility of them. This ratio grows exponentially at a rate with a base of $e$ as we have shown. This seems to be a fundamental theorem about the nature of reversibility. This gives us a hint as to how we can asymptotically approximate $n!$. Abraham De Moivre demonstrated that $n!$ grows at the rate of $\frac{n^n}{e^n}$ times $\sqrt{n}$ as well as some constant left to be determined later. $$n! \sim c \sqrt{n} \frac{n^n}{e^n}$$ Stirling then proved that the constant is equal to the square root of $2\pi$ which produces Stirlings formula for the factorial. $$n! \sim \sqrt{2\pi n} \frac{n^n}{e^n}$$ This equation given by Stirling is the full asymptotic definition of the factorial function. The appearance of $e$ in the asymptotic definition of factorial also gives some insight into why it is that the reciprocals of the factorials happen to converge to $e$.

Monday, October 15, 2018

Base of differential fixed points

Consider the definition of the difference quotient in terms of the quotient produced by an interval of length $h$. $$\frac{f(x+h)-f(x)}{h}$$ We want to study the fixed points of this difference quotient, supposing that $h$ is fixed. In order to do so we can equate $h$ with $f(x)$. To simplify this equation we can multiply both sides by $h$ and then add $f(x)$ to both sides. $$\frac{f(x+h)-f(x)}{h}=f(x)$$ $$f(x+h)-f(x)=hf(x)$$ $$f(x+h)=(h+1)f(x)$$ At this point we can raise $h+1$ to the power of $1/h$ to get the base of the fixed point of difference quotient with fixed length $h$. $$b = (h+1)^{\frac{1}{h}}$$ This formula works in general to compute the base of the fixed point of a difference quotient of any given length. We tend to want to reduce our consideration to the case of unit fractions $1/n$ in which case we get the following familiar formula for the base of the differential of the fixed point of a given unit fraction length: $${(\frac{n+1}{n})}^n$$ Actual values of this sequence of rational numbers are provided below. The first case $2$ is the fixed point of the difference quotients of length $2$ or the difference quotients of length $1$, the next number $9/4$ is the base of the difference quotients of length $1/2$, and the next is the base of the difference quotients of length $1/3$, and so on. $$2, \frac{9}{4}, \frac{64}{27}, \frac{625}{256}, \frac{7776}{3125} ...$$ As a result, in the case of finite differences it is possible to use $2^x$ as a fixed point. The consecutive differences of the $2^x$ sequence are the values of $2^x$ itself. But this $2^x$ value does not suffice when taking difference quotients of smaller lengths. $$1,2,4,8,16,32,64,128,256,...$$ In order to get the fixed point of the difference quotients of smaller lengths it is necessary to use the formula ${(\frac{n+1}{n})}^n$ we derived earlier to get a different base. If we then continue this process to infinity we get the base of the fixed point of the derivative which is $e$ which leads to the function $e^x$ which is equal to itself under differentiation. This demonstrates that the limit ${(\frac{n+1}{n})}^n$ is not simply a random means of generating $e$ it is actually a formula for the different fixed points of the difference quotient. So actually the identity of $e$ is as the fixed point of the derivative and the limit definition is just computing different fixed points of the difference quotient.

Thursday, October 11, 2018

Order theory and mathematical analysis

Asymptotic analysis describes the limiting behavior of a function as it approaches infinity. Using asymptotic analysis, we have notions of different rates of growth, so for example, we can have linear, polynomial, or exponential growth rates among others. We can extend this notion to totally order functions by their growth rate, so that growth rates are roughly totally ordered. Though this totally ordered structure is not going to be an ordinary one.

Through the use of order theory, we can extend the real numbers to get non-Archimedean ordered fields that contain both infinite and infinitesimal elements. This includes ordered fields such as the surreal numbers as well as the transseries which characterize growth rates. It has even been shown that the field of transseries carries the structure of the surreal numbers. This shows that the growth rates of functions form the most general order worth studying. This directly applies order theory to asymptotic analysis.

Asymptotic analysis is directly related to the calculus because the derivatives of functions are really another way of looking at the growth rate. So really by looking at order theory, we can see how it is directly applicable to most of mathematical analysis already.

Metric spaces are already explicitly defined in a way that relates them to order theory, as they use an order to relate their distances to one another. Something must be closer to something else in an ordered fashion. Recently, I demonstrated that metric spaces are directly related to the order topology of their set of distances. The order topology of the set of distances places a limit on the topology of the metric space. This demonstrates that really practically all of mathematical analysis can benefit from the use of order theory.

But the relationship goes back in the other direction too because of the order topology. Given any partially ordered set we can explore the topological properties of the order using the open sets formed from it. This shows that topological notions like isolated points can be applied to any partial order. This demonstrates the analytic and topological nature of order theory itself.

Really, metric spaces, orders, and so on are all united by the common thread of topology. Really, it can be said that the common thread at the root of different aspects of mathematical analysis is topology. Orders have a topology on them, and metrics have a topology on themselves and their distance order. As it happens, I consider orders and metrics to be two of the most important structures so thinking about them, the relationship between them, and relating that back to topology has consumed much of my attention.

Tuesday, October 9, 2018

Rates of convergence

Given a sequence of rational numbers that sequence can either converge or diverge. If it converges to some point in the number line, then it does so at some rate. It can either converge to a rational number or to an irrational number. If it converges to some rational number then it is equal to some rational number plus or minus some infinitesimally small sequence that converges to zero. It is well known, for example, that the reciprocal 1/n converges to zero, so a number like 5+1/n converges to 5. The reciprocal of another function like 1/n^2 converges to zero quickly, so 5+1/n^5 converges to 5 quicker then 5+1/n. This difference is expressed in rates of convergence.

If we have some sequence that converges to an irrational number, then the same principle applies analogously. Consider the Leibniz formula, it converges to pi, but it does so extremely slowly. In order to get an accurate approximation of pi, it is not a very efficient sequence to use. The Ramanujan formula and Chudnovsky formula converge much faster. This shows that irrational numbers can be approximated to a greater or better extent by different sequences. An irrational number can then be defined be the most convergent sequence that is currently available. This is similar to defining them by equivalence classes, except this allows you to actually compute rational approximations.