On Tue, Feb 11, 2025 at 02:44:20PM +0000, Martin Baker wrote:
> On 09/02/2025 17:45, Waldek Hebisch wrote:
> > Finite topological spaces are equivalent to partial orders, so
> > there is connection to logic. But they are quite different than
> > infinite topological spaces like simplicial complexes.
>
> I hope there is a way to implement a 'geometric realization' function,
> that is an algorithm to embed a finite topological space in a vector
> space (which is a Euclidean space, which is a topological space).
I am affraid there is confusion what "finite topological space"
means. By this I mean finite set with topology. Simplest
nontrivial example is two element set {a, b}, with topology
{{}, {a}, {a, b}}. Nontrival here means that this in neither
discrete topology nor anti-discrete one. There is a theorem
saying that any finite subset of euclidean space has discrete
topology. So, to have non-trivial topology on a subset of
euclidean space you must have an infinite set. So
'geometric realization' can only work for "nice" spaces
and gives interesting results only for infinite ones.
Actually, there is notion of topological dimension which
for separable metric spaces say that space of dimension n
can be topologically embedded in euclidean space of
dimension 2*n + 1.
Note that "finite simplicial complexes" are typicall
infinite topological spaces, the word "finite" means
that there is finite number of pieces, but typicall
some pieces are infinite.
> In the
> opposite direction I would also like to implement a 'nerve
> construction'. I would also like to link these to logic/frames as in
> Steven Vickers book 'Topology via Logic' but at this stage I am just
> trying to work out what's possible.
I have not seen Vickers book.
> > Let me present my view here. What does it mean "doing mathematics
> > in computer"? One aspect is to support notation analogus to used
> > in literature, allowing creation and manipulation of statements/
> > expressions. In particular this means reasonably nice output.
> > Basicaly this would be "programmable editor", so transformation
> > could be specified by hand.
>
> Are you talking about a graphical editor for Topology/Geometry that
> would give an equation editor and draw the result in real time? This
> would be very nice but not the sort of thing that could be written in SPAD?
I had in mind symbolic/textual representation (and going beyond
Geometry). It would be nice to have grapical presentaion and
editor, but to sensibly connect this to other parts of FriCAS
the core representation should be symbolic. And currently we
have limited support for graphic in Spad, in particular
interaction is limited to a handful of special cases. So
going graphical here would be a big project.
> > Nontrivial mathematical statements
> > may be hard or impossible to decide, so I do _not_ expect
> > general domain of this sort to be able to say decide mathematical
> > equality. But hopefully user should be able to specify
> > transformations and see their effect.
>
> Well for finite topology code (as opposed to the existing simplicial
> complex code in alg_top.spad) I would like the 'equalities' to be
> Homeomorphism (a cup is the same as a doughnut) and homotopy equivalence
> (a line is the same as a point). Since these are defined like
> isomorphism with maps in both directions I would like some way to
> create, combine and use continuous maps. So I think I would need a
> domain to represent a continuous map. Presumably as a subset of a
> product, that is, a set of (input,output) pairs for the points combined
> with something similar in the reverse direction for the open set
> preimage. This all seems very messy and unwieldy which is why I like the
> idea of implementing it as database tables.
Well, you write "finite", but in fact main point here is that
you need handle infinte spaces. More precisely, you want to
avoid actual infinity, so you need to represent things that
mathematically are infinite using finite amout of information.
Already fact that finite amout of information is enough is
mathematically quite non-trivial and one needs smart approach
to get results using managable ampount of information, that
is why I mentioned Sergeraert below.
Mathematically, databases are trivial. They embody large
number of tricks to speed up typical business data processing,
but are unlikely to be relevant for the problem. At best
thinking about databases is premature optimization.
> I know there is a database
> domain in FriCAS but I think that's just for internal FriCAS metadata?
The Database domain is general, but it is essentially association
list with some tweaks. As Ralf wrote, for fast access to largish
amount of data hash tables are typically better (lists are faster
for small number of entries).
Traditionally FriCAS uses term "database" when speaking about
internal data, but this is want is usually called "symbol table".
ATM FriCAS has no true databases (but hash tables may be better
for ypur problem).
> One advantage of having a database is that it makes it easier to
> implement a pullback which seems to be the fundamental construct where a
> lot of this structure comes from. So this would be a database search
> which would only enable the inputs which go to the same place when they
> go different ways around the square.
Actually, pullback is rather easy: you have a function f from
S1 to S2 and some data associated to points in S2. You want
to get data corresponding to point s in S1. To get it you
just apply f to s getting f(s) \in S2. And then you look up
appropiate data in S2. Push-forward is more tricky, as you
may be forced to find counterimages of point s \in S2. And
actually main work here is to sensibly represent functions and
spaces and whatever data you need to associate with points.
In fact, in many cases data is associated with subsets and doing
such thing naively (as table giving value for each subset)
leads to trouble even if you consider moderatly large finite
spaces.
Just as an example, consider lattice of subgroups of a finite
group G. One naive approach could be: consider all subsets
of G, for each subset compute group generated by this subset,
getting collection (list) of subgoups of G. Trouble is, that
group having 60 elements is quite small, but set of subsets is
too large to enumenrate is reasonable time on current machines.
OTOH number of subgroups seem to be much smaller and for
groups having less than 100 elements it is probably not too
hard to create list of all subgroups. I do not know if there
are good methods working for bigger groups, but worst case
that I found are vector spaces over Z_2, where number of
subgroups is of order N log(N), where N is number of elemnts
of the group (and in such very special case it is easy to
generate list of subgroups).
> > For classical topological spaces people care about homotopies and
> > homology. Homology for simplicial complexes essentially reduces to
> > linear algebra over integers, so is relatively easy. First homotopy
> > group is in general uncomputable. Assuming that first homotopy
> > group is trivial, there is old result about higher homotopy groups,
> > namely there is relation to homology of loop spaces. Loop spaces
> > as normally defined are not simpilical complexes, but it is
> > relatively easy to give infinite simpilical complex which is
> > homotopy equvalent to loop space of a simplical complex. So
> > one needs to tame infinity. One step here was done by E. Brown,
> > who proved that to compute homotopy of given order is is enough
> > to look at finite part of infinite simpilical complex equivalent
> > to loop space. Complex given by Brown is quite large. F. Sergeraert
> > showed that one can use much smaller finite complex, which allowed
> > practical computations. AFAICS there is rather heavy theory
> > behind this and implementation needs a lot of coding.
> >
> > Vector bundles over simplicial complexes have rather natural
> > representation: over each simplex you have vector space
> > of given dimension, so by choosing basis you can just take
> > R^n. On intersection of simplexes there is change of base,
> > so you need a transition matrix. In general this transition
> > matrix may be an arbitrary continous matrix function, subject
> > to agreement rules. But you should be able to do with
> > matrix valued polynomials (or rational functions since we need
> > inverses). And AFAICS homotopic sets of transition matrices
> > give isomorphic bundles, so there is more possibilities to
> > limiot form of transition matrices. If transition matrices
> > take values in orthogonal matrices you should be able to
> > represent bundles of spheres in similar way. If transition
> > matrices have integer entries and determinant +-1 you will
> > get bundles of toruses.
> >
> > In somewhat different direction you may consider algebraic
> > sets. CAD (implementd by CylindricalAlgebraicDecompositionPackage)
> > give you decomposition of real algebraic set into cells,
> > so you should be able to produce a simplicial complex from
> > such decomposition. If the set is smooth you may consider
> > tanget bundle or normal bundle.
> >
> > I think that analog of cylindrical algebraic decomposition
> > works for more general sets, defined by elementary equations
> > and inequalities (with reasonable regularity assumptions needed
> > to avoid uncomputability). But again, this probaly would
> > require working out details of theory (I am not aware of
> > precise description) and coding is likely to be rather
> > involved.
> >
> > I would suggest to start with relatively simple things and
> > make them work well, so simplicial complexes rather than
> > generalizations, functions which are as simple as possible
> > (for mappings one gets nontrivial theory already from
> > piecewise linear maps).
>
> Are you saying that the existing simplicial complex code in alg_top.spad
> needs reworking? I would like to improve this and add simplicial sets
> (like simplicial complex but based on a weak order). Before I look at
> this I want to learn more about the fundamentals of finite topological
> spaces and implement some code for that.
I think that simplicial complexes work quite well. OTOH cubical
and delta complexes were not really finished and there were little
progress after they were commited. Based on what is already
implemented for simplicial complexes one can do more things.
I suggest avoid small variations which add only a little functionality,
but may cause significant extra work (AFAIR it turned out that
_correct_ implementation of some aspects of cubical and delta
complexes is more tricky than for simplical ones). Also, do
not be too ambitious, setting to far goal is good recipe for
failure. Finally, things really should be tested with reasonable
coverage.
> I am interested in the link to cylindrical algebraic decomposition you
> mention so I will investigate that more and see if it can be linked to
> the structures in alg_top.spad or new topology code. I assume there are
> no tutorials for the CAD package?
Classic CAD (that is algebraic case) is well covered in literature.
Basic idea is explaned in Davenport book on computer algebra
available from his webpage (and from other places). We have a
test file in the repo and an example in wiki. To say the
truth, current code is geared toward problem of deciding validity
of statements. To conveniently solve other problems we need
more code, probably exposing some data that is computed inside
CAD package, but not shown in final result. And we need to
wrap it in convenience domain/packages for easier use in other
problems.
--
Waldek Hebisch
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to fricas-devel+unsubscr...@googlegroups.com.
To view this discussion visit
https://groups.google.com/d/msgid/fricas-devel/Z6ztzxmPCF3p9WJs%40fricas.org.
