SelectedPapers.net launched!

As many people know, academia  fights to break free from the chains of legacy publishers. And apparently it’s on the way to succeed.  Unlike the  fully automated Academic Skynet,  which is still in a very early draft version, the human-edited  SelectedPapers.net  is now launched.

OK. fun aside, this could prove to be an excellent initiative, DEPENDING ON YOU.  The limit of this system is only your imagination. Try it, play with it, disseminate it.

Congratulations to Christopher Lee and John Baez for this project. Here are two posts (at Baez blog) explaining what this is about:

In few words, it is a tag system for articles in arxiv or PubMed (or with a DOI) which is designed to work, in principle, with any existing social network. For the moment it works in association with G+ (i.e. posts on G+ with the hashtags #spnetwork  arxiv:1234.5678  are automatically retrieved by spnetwork).

But even in this stage, one can use a G+ post to connect, say, an arxiv article with something from a third place. I used this trick in this post, in order to signal that  arXiv:1305.5786  has an associate web tutorial page on this blog. It worked smoothly!

So, what about open peer reviews? Other ideas?

__________

UPDATE: Timothy  Gowers  has a post where he explains what he intends to do with/for  the spnetwork. Especially interesting part:

But the other reason for writing the post is that I hope it will encourage others to do similar things: even if 1000 mathematicians each wrote just one review, that would already create a site worth exploring, and in principle it could happen very quickly.

__________

UPDATE 2:  I just put on my web page the following:

READ THIS: I recommend the use of The Selected Papers Network. Look at these two posts by John Baez to understand how it works: spnetwork (Part 1) , spnetwork (Part 2). If you wish to notice me about your recent (or older) arxiv articles which you think I might benefit from and comment about them then send me a mail or connect with me on G+.

__________

UPDATE 3:    Would it be possible to blend the human edited spnetwork with an automatic service like NewSum?    After all, the start of this post is only a half joke.

Dictionary from emergent algebra to graphic lambda calculus (I)

Because I am going to explore in future posts the emergent algebra sector, I think it is good to know where we stand with using graphic lambda calculus for describing proofs in emergent algebra as computations.  In the big map of research paths, this correspond to the black path linking “Energent algebra sector” with “Emergent algebras”.

A dictionary seems a good way to start this discussion.

Let’s see, there are three formalisms there:

  • in the first paper on spaces with dilations, Dilatation structures I. Fundamentals arXiv:math/0608536  section 4,  is introduced a formalism using binary decorated trees in order to ease the manipulations of dilation structures,
  • emergent algebras are an abstraction of dilation structures, in the sense that they don’t need a metric space to live on. The first paper on the subject is Emergent algebras arXiv:0907.1520   (see also Braided spaces with dilations and sub-riemannian symmetric spaces  arXiv:1005.5031  for explanations of the connection between dilation structures and emergent algebras, as well as for braided symmetric spaces, sub-riemannian symmetric spaces, conical groups, items you can see on the big map mentioned before). Emergent algebras is a mixture of an algebraic theory with an important part of epsilon-delta analysis.  One of the goals of graphic lambda calculus is to replace this epsilon-delta part by a computational part.
  • graphic lambda calculus, extensively described here, has an emergent algebra sector (see  arXiv:1305.5786 , equally check out the series Emergent algebras as combinatory logic part I, part II, part IIIpart IV,  ). This is not an algebraic theory, but a formalism which contains lambda calculus.

The first figure describes a dictionary of objects which appear in these three formalisms. In the first column you find objects as they appear in dilation structures – emergent algebra formalism. In the second column you find the corresponding object in the binary trees formalism. In the third column there are the respective objects as they appear in the emergent algebra sector of the graphic lambda calculus.

sum_basic

Some comments: the first two rows  are about an object called

  • “dilation (of coefficient \varepsilon, with \varepsilon \in \Gamma, a commutative group)” in dilation structures,  which is a operation in emergent algebras, indexed by \varepsilon, (the second row is about dilations of coefficient \varepsilon^{-1}),
  • it is an elementary binary tree with the node decorated by white (for \varepsilon) or black (for \varepsilon^{-1})
  • it is one of the elementary gates in graphic lambda calculus.

The third row is about the “approximate sum” in dilation structures, which is a composite operation in emergent algebras, which is a certain graph in graphic lambda calculus.

The fourth row is about the “approximate difference” and the fifth about the “approximate inverse”.

For the geometric meaning of these objects see the series on  The origin of emergent algebras part I, part II, part III,   or go directly and read arXiv:1304.3694 .

What is different between these rows?

  • In the first row we have an algebra structure based on identities between composites of operations defined on a set.
  • In the second row we have trees with leaves decorated by labels from an alphabet (of formal variables) or terms constructed recursively from those  .
  • In the third row we have graphs with no variable names. (Recall that in graphic lambda calculus there are no variable names. Everything written in red can be safely erased, it is put there only for the convenience of the reader.)

Let’s see now the dictionary of identities/moves.

moves_basic

The most important comment is that identities in emergent algebras become moves in the other two formalisms. A succession of moves is in fact a proof for an identity.

The names of the identities or moves have been commented in many places, you see there names like “Reidemeister move” which show relations to knot diagrams, etc. See this post for the names of the moves and relations to knot diagrams, as well as section 6 from  arXiv:1305.5786 .

Let’s read the first column: it says that from an algebraic viewpoint an emergent algebra is a one parameter family (indexed by \varepsilon \in \Gamma) of idempotent right quasigroups. From the geometric point of view of dilation structures, it is a formalisation of properties expected from an object called “dilation”, namely that it preserves the base-point ( “x” in the figure), that a composition of dilations of coefficients \varepsilon, \mu, with the same base-point,  is again a dilation, of coefficient \varepsilon \mu, etc.

In the second column we see two moves, R1 and R2, which can be applied anywhere in a decorated binary tree, as indicated.

In the third column we see that these moves are among the moves from graphic lambda calculus, namely that R1 is in fact related to the oriented Reidemeister move R1a, so it has the same name.

The fact that the idempotent right quasigroup indexed by the neutral element of \Gamma, denoted by 1, is trivial, has no correspondent for binary trees, but it appears as the move (ext 2) in graphic lambda calculus. Through the intermediary of this move appears the univalent termination gate.

These are the common moves. To these moves add, for the part of the emergent algebra sector, the R1b move, the local fan-out moves and some pruning moves. There is also the global fan-out move which is needed, but we are going to replace it by a local move which has the funny name of “linearity of fan-out”, but that’s for later.

The local fan-out moves and the pruning moves are needed for the emergent algebra sector but not for the binary trees or emergent algebras. They are the price we have to pay for eliminating variable names. See the algorithm for producing graphs from lambda calculus terms, for what concerns their use for solving the same problem for untyped lambda calculus. (However, the emergent algebra sector is to be compared not with the lambda calculus sector, but with the combinatory logic sector, more about this in a further post.)

We don’t need all pruning moves, but only one which, together with the local fan-out moves, form a family which could be aptly called:

co_mono_y

(notice I consider a reversible local pruning)

Grouping moves like this makes a nice symmetry with the fact that \Gamma is a commutative group, as remarked here.

As concerns the R1b move, which is the one from the next figure, I shall use it only if really needed (for the moment I don’t). It is needed for the knot diagrams made by emergent algebra gates sector, but it is not yet clear to me if we need it for the emergent algebra sector.

r1bmove

However, there is a correspondent of this move for emergent algebras. Indeed, recall that a right quasigroup is a a quasigroup if the equation x \circ a = b  has a solution, which is unique. If our emergent algebra is in fact a (family of) quasigroup(s) , as happens for the cases of conical groups or for symmetric spaces in the sense of Loos (explained in arXiv:1005.5031 ), then in particular it follows that the equation  x \circ_{\varepsilon} a = a has only the solution x = a (for \varepsilon \not = 1). This last statement has the R1b move as a correspondent in the realm of the emergent algebra sector.

Until now we have only local moves in the emergent algebra sector. We shall see that we need a global move (the global fan-out) in order to prove that the dictionary works, i.e. for proving the fundamental identities of emergent algebras within the graphic lambda calculus formalism. The goal will be to replace the global fan-out move by a new local move (i.e. one which is not a consequence of the existing moves of graphic lambda calculus). This new move will turn out to be a familiar sight, because it is related to the way we see linearity in emergent algebras.

A map of research paths and subjects touched on this blog

The map is not complete, I intend to modify it in time. I would love to have an enhanced version of this map with the possibility to click on the nodes and on the edges of the graph and get as a result a list of links to posts and articles, or any other material.  How can I do that?

Here is the map. With red are marked nodes or paths which have been explored (or which are trivial, like the path linking qubits and vector spaces, for example). With black are marked the nodes or paths which I intend to explore.

bigmap

Not present on this map are subjects which interest me a lot, like understanding vision, neural connectomics and other subjects related to computing with space.

Categorical decorations of the emergent algebra sector, I

The emergent algebra sector of graphic lambda calculus is described in   arXiv:1305.5786  section 5 .  By a categorical decoration of the graphs from this sector I mean  representing such graphs as if the edges are arrows in a category. In this first post I sketch what I need, later I shall streamline everything, so don’t take anything at face value, but more with an exploratory, gaming attitude. Comments are welcomed.

The CO-COMM and CO-ASSOC moves are part of the moves which define this sector, along with the emergent algebra moves.  The first group of moves suggests to use a category with finite coproducts and with nontrivial cocommutative cogroupsThis would make things symmetric, because \Gamma is a commutative group.

So we have a cocommutative group object M with operation \Upsilon: M \rightarrow M \vee M, a commutative group object \Gamma  with operation \cdot : \Gamma \times \Gamma \rightarrow \Gamma … and an operation \delta: M \times G \rightarrow Hom(M,M), which suggests  we need a category with finite products and coproducts, with interesting commutative group and cocommutative cogroup objects.  The rules of decorations are the following (the first line tells that to the gate \bar{\varepsilon} corresponds a composite of the \delta operation with the evaluation eval: Hom(M,M) \times M \rightarrow M . (Alternatively, the edge marked with “1” in the first diagram, along with M, may give an object (1,M), to explore.)

r2_cat_0

These arrows have to be compatible in the sense that they can be used to represent the emergent algebra moves. (Other constraints will follow.) For example, in the case of the R2 move the composition from the upper side of the figure have to be equal with the composition from the lower side of the figure:

r2_cat_1

I am interested in funny, crazy examples, (homotopy theory? combinatorics?), do you have any? If not yet, then wait for the sequel, or help me to clarify this subject.

UD, A-buffer, surfels

That’s a collection of facts which might be interesting for UD seekers. I’ll just dump it and wait for your reaction.

(from this wiki page) “Loren Carpenter is co-founder and chief scientist of Pixar Animation Studios. He is the co-inventor of the Reyes rendering algorithm. … In 1980 he gave a presentation at the SIGGRAPH conference, in which he showed “Vol Libre”, a 2 minute computer generated movie. This showcased his software for generating and rendering fractally generated landscapes, and was met with a standing ovation, and (as Carpenter had hoped) he was immediately invited to work at Lucasfilm‘s Computer Division (which would be come Pixar).[2] There Carpenter worked on the “genesis effect” scene of Star Trek II: The Wrath of Khan, which featured an entire fractally-landscaped planet.[2]

… Carpenter invented the A-buffer hidden surface determination algorithm.”

Here is a link to the paper The A-buffer, an Antialiased Hidden Surface Method (1984), recommended reading.

_____

(from this wiki page) “Hidden surface determination is a process by which surfaces which should not be visible to the user (for example, because they lie behind opaque objects such as walls) are prevented from being rendered. Despite advances in hardware capability there is still a need for advanced rendering algorithms. The responsibility of a rendering engine is to allow for large world spaces and as the world’s size approaches infinity the engine should not slow down but remain at constant speed. Optimising this process relies on being able to ensure the diversion of as few resources as possible towards the rendering of surfaces that will not end up being rendered to the user.

There are many techniques for hidden surface determination. They are fundamentally an exercise in sorting, and usually vary in the order in which the sort is performed and how the problem is subdivided. Sorting large quantities of graphics primitives is usually done by divide and conquer.”

_____

For surfels see this page.

Surfels: Surface Elements as Rendering Primitives
H. Pfister, M. Zwicker, J. van Baar, M. Gross, SIGGRAPH 2000

A Survey and Classification of Real Time Rendering Methods
M. Zwicker, M. Gross, H. Pfister
Technical Report No. 332, Computer Science Department, ETH Zürich, 1999.

From the first mentioned article: “In this paper we propose a new method of rendering objects with rich shapes and textures at interactive frame rates. Our rendering architecture is based on simple surface elements (surfels) as rendering primitives. Surfels are point samples of a graphics model. In a preprocessing step, we sample the surfaces of complex geometric models along three orthographic views. At the same time, we perform computation-intensive calculations such as texture, bump, or displacement mapping. By moving rasterization and texturing from the core rendering pipeline to the preprocessing step, we dramatically reduce the rendering cost.”

______

Does it look a bit familiar?

Ramsey theorem and ultrafilters (II)

This is a continuation of the post Has Ramsey theorem anything to do with the ultrafilter monad?  In this post I want to write the shortest proof of Ramsey theorem (in finite or infinite version) I can make for the moment. This is probably well-known, please tell me if so, with references, and I shall update the post.

The motivation is the fact that I don’t get why one has to reason by compactness and contradiction, so I am looking for a direct proof (which is of course still non constructive).

Notation: for any k \in \mathbb{N} with k > 0,  we denote by [k] the set \left\{ 1, ... , k \right\} and by \lceil k \rceil the set \left\{0,1, ... , k\right\}.

Definition: A function c: \mathbb{N} \times \mathbb{N} \times \mathbb{N} \rightarrow \lceil k \rceil is a kcolor if it has the following distance-like properties

  • it is symmetric, i.e. for any permutation (abc) of the set [3] and for any x, y, z \in \mathbb{N} we have c(x_{a}, x_{b}, x_{c}) = c(x_{1}, x_{2}, x_{3}),
  • it is reflexive, i.e. for any x \leq y \leq z in \mathbb{N}c(x,y,z) = 0 if and only if x=y.

Explanation: a sequence of coloured complete graphs K_{n} is a function c(x,y,n) = c_{n}(x,y), defined for any x<y (in order to colour the non-oriented edge from x to y) and for any y \leq n (because is a colouring of the complete graph with n vertices). We complete the colouring by c(x,x,n) = 0.  In case the color function does not depend on n then it’s just a colouring of K_{\infty}.

Fact. Any color function admits an unique continuous extension to U\mathbb{N}^{3} , which is identified with \left(U\mathbb{N}\right)^{3}.

Proof of Ramsey theorem: for any non-principal ultrafilter \beta \in U\mathbb{N} \setminus \mathbb{N}, there exists and is  unique a colour j \in [k] such that c(\beta, \beta, \beta) = j. By continuity,

\lim_{x \rightarrow \beta} \lim_{y \rightarrow \beta} \lim_{n \rightarrow \beta} c(x,y,n) = j.

Can you see why this is Ramsey theorem? [added: curry and lazy evaluate, so to say, the three limits.]

Guestpost: a proposal of a UD like algorithm by Bauke Conijn

The following is the first guest post, answering the invitation made in  Call for analysis of the new UD video .  The author is Bauke Conijn (aka bcmpinc). Reposted on his blog here.

______________

I designed an algorithm that, given an octree and a location within that octree can compute the cubemap at that location. The algorithm kind of raytraces each face of the cubemap, but does this in such a way that  multiple rays are traced simultaneously (aka. mass connected processing).

The faces of the cubemap are axis-aligned, which allows us to use linear interpolation rather than perspective correct interpolation (which includes 2 multiplications and a division). Because of this linear
interpolation, the algorithm only needs integer additions, subtractions,  and multiplications by a power of two (aka. bitshifts).

For a more thorough explanation of the algorithm please read this article.

I’ve also written a partial implementation of the algorithm, available at Git-hub, which renders the positive z plane of the cubemap. It currently does so at 2 fps, which, considering I did not yet put effort in optimization and screen space occlusion is not yet implemented, seems  promising. The data is still fully loaded into memory at startup. As background I render a fixed cubemap.

Due to space considerations, not all models have been uploaded to  git-hub, but a small low-resolution model is available, such that after compiling the code, you can at least see something. The code is rather  messy as it is still in an experimental state.

Images:
http://imageshack.us/a/img839/7291/voxel2.png (test-scene)
http://imageshack.us/a/img841/1796/voxel3.png (test-scene)
http://imageshack.us/a/img708/221/voxel4.png (part of Mouna Loa)
http://imageshack.us/a/img24/8798/voxel5.png (part of Mouna Loa)
http://imageshack.us/a/img69/2483/voxel6.png (low resolution)

_______________

UPDATE: Here is a movie made by Bauke, with his program.

Moreover, here is a draft article which explains it in detail.