On Wed, Feb 12, 2025 at 12:52 PM Waldek Hebisch <de...@fricas.org> wrote:
>
> 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.
the basic notion is an "abstract" simplicial complex.
It should not be confused with a "geometric simplicial complex" (an
embedding of an abstract one into a space of some sort, e.g an
Euclidean space.)
A finite abstract simplicial complex is a purely combinatorial object.
One can study its homology groups, over a finite field (e.g.
Z_2-homology is very common)
without resorting to Euclidean spaces.
E.g. SageMath can compute such things:
S = SimplicialComplex([[0,1], [1,2], [0,2]]) # circle
T = S.product(S) # torus
Simplicial complex with 9 vertices and 18 facets
sage: T.homology(base_ring=GF(2))
{0: Vector space of dimension 0 over Finite Field of size 2,
1: Vector space of dimension 2 over Finite Field of size 2,
2: Vector space of dimension 1 over Finite Field of size 2}
Just in case,
Dima
>
> > 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.
--
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/CAAWYfq0kOdOCsRxneHz9TmFYHYzh%3DaYA-7qW4MMMqOe%2BuCvxxQ%40mail.gmail.com.
