Generic solutions to polynomial equations in distributive categories
Date: July 18th (Thursday)
Time: 15:25-15:45
Abstract
Following a remark of Lawvere, Blass exhibited a particularly elementary
bijection between the set of binary trees, and seven tuples of binary trees. A "set of binary
trees" may be abstracted to "an object $T$ of a distributive category with a given
isomorphism $T^2 + 1 \cong T$". Particularly elementary in fact means "constructible from
the given isomorphism using distributive category operations". In this context, it is seen that
there is no such bijection for pairs, triples, ..., six-tuples of binary trees.
The author has described, for a given polynomial P, the free distributive category containing
an object $X$ and given isomorphism $P(X) \cong X$, and the isomorphism classes of this
category. Since distributive operations correspond to the operations used to build straightline
circuits/programs from simpler circuits/programs, the results of the author may be
interpreted as proving the existence/non-existence of isomorphims constructible by straight
line circuits/programs.
The talk will briefly describe the connection between distributive categories and circuits, the
bijection presented by Blass, the techniques used and results acheieved for the general case,
and some speculation on future directions.
