Дисертації з теми "Finite algebraic structures"

Cette thèse contribue à une recherche de modèles finis et à la démonstration automatisée de théorèmes, en se concentrant principalement, mais sans s'y limiter, sur les méthodes d'intelligence artificielle. Dans la première partie, nous résolvons une question de recherche ouverte à partir de l'algèbre abstraite en utilisant une recherche automatisée de modèles finis massivement parallèles, en utilisant l'assistant de preuve Isabelle. À savoir, nous établissons l'indépendance de certaines lois de distributivité abstraites dans les binaires résiduels dans le cas général. En tant que sous-produit de cette découverte, nous apportons un client Python au serveur Isabelle. Le client a déjà trouvé son application dans les travaux d'autres chercheurs et de l'enseignement supérieur. Dans la deuxième partie, nous proposons une architecture de réseau neuronal génératif pour produire des modèles finis de structures algébriques appartenant à une variété donnée d'une manière inspirée des modèles de génération d'images tels que les GAN (réseaux antagonistes génératifs) et les autoencodeurs. Nous contribuons également à un paquet Python pour générer des semi-groupes finis de petite taille comme implémentation de référence de la méthode proposée. Dans la troisième partie, nous concevons une architecture générale de guidage des vérificateurs de saturation avec des algorithmes d'apprentissage par renforcement. Nous contribuons à une collection d'environnements compatibles OpenAI Gym pour diriger Vampire et iProver et démontrons sa viabilité sur des problèmes sélectionnés de la bibliothèque TPTP (Thousand of Problems for Theorem Provers). Nous contribuons également à une version conteneurisée d'un modèle ast2vec existant et montrons son applicabilité à l'incorporation de formules logiques écrites sous la forme clausal-normale. Nous soutenons que l'approche modulaire proposée peut accélérer considérablement l'expérimentation de différentes représentations de formules logiques et de schémas de génération de preuves synthétiques à l'avenir, résolvant ainsi le problème de la rareté des données, limitant notoirement les progrès dans l'application des techniques d'apprentissage automatique pour la démonstration automatisée de théorèmes
This thesis contributes to a finite model search and automated theorem proving, focusing primarily but not limited to artificial intelligence methods. In the first part, we solve an open research question from abstract algebra using an automated massively parallel finite model search, employing the Isabelle proof assistant. Namely, we establish the independence of some abstract distributivity laws in residuated binars in the general case. As a by-product of this finding, we contribute a Python client to the Isabelle server. The client has already found its application in the work of other researchers and higher education. In the second part, we propose a generative neural network architecture for producing finite models of algebraic structures belonging to a given variety in a way inspired by image generation models such as GANs (generative adversarial networks) and autoencoders. We also contribute a Python package for generating finite semigroups of small size as a reference implementation of the proposed method. In the third part, we design a general architecture of guiding saturation provers with reinforcement learning algorithms. We contribute an OpenAI Gym-compatible collection of environments for directing Vampire and iProver and demonstrate its viability on select problems from the Thousands of Problems for Theorem Provers (TPTP) library. We also contribute a containerised version of an existing ast2vec model and show its applicability to embedding logical formulae written in the clausal-normal form. We argue that the proposed modular approach can significantly speed up experimentation with different logic formulae representations and synthetic proof generation schemes in future, thus addressing the data scarcity problem, notoriously limiting the progress in applying the machine learning techniques for automated theorem proving

This thesis mainly concerns the cohomology of the moduli spaces ℳ3[2] and ℳ3,1[2] of genus 3 curves with level 2 structure without respectively with a marked point and some of their natural subspaces. A genus 3 curve which is not hyperelliptic can be realized as a plane quartic and the moduli spaces 𝒬[2] and 𝒬1[2] of plane quartics without respectively with a marked point are given special attention. The spaces considered come with a natural action of the symplectic group Sp(6,𝔽2) and their cohomology groups thus become Sp(6,𝔽2)-representations. All computations are therefore Sp(6,𝔽2)-equivariant. We also study the mixed Hodge structures of these cohomology groups. The computations for ℳ3[2] are mainly via point counts over finite fields while the computations for ℳ3,1[2] primarily uses a description due to Looijenga in terms of arrangements associated to root systems. This leads us to the computation of the cohomology of complements of toric arrangements associated to root systems. These varieties come with an action of the corresponding Weyl group and the computations are equivariant with respect to this action.

Algebraic theories describe mathematical structures that are defined in terms of operations and equations, and are extremely important throughout mathematics. Many generalisations of the classical notion of an algebraic theory have sprung up for use in different mathematical contexts; some examples include Lawvere theories, monads, PROPs and operads. The first central notion of this thesis is a common generalisation of these, which we call a proto-theory. The purpose of an algebraic theory is to describe its models, which are structures in which each of the abstract operations of the theory is given a concrete interpretation such that the equations of the theory hold. The process of going from a theory to its models is called semantics, and is encapsulated in a semantics functor. In order to define a model of a theory in a given category, it is necessary to have some structure that relates the arities of the operations in the theory with the objects of the category. This leads to the second central notion of this thesis, that of an interpretation of arities, or aritation for short. We show that any aritation gives rise to a semantics functor from the appropriate category of proto-theories, and that this functor has a left adjoint called the structure functor, giving rise to a structure{semantics adjunction. Furthermore, we show that the usual semantics for many existing notions of algebraic theory arises in this way by choosing an appropriate aritation. Another aim of this thesis is to find a convenient category of monads in the following sense. Every right adjoint into a category gives rise to a monad on that category, and in fact some functors that are not right adjoints do too, namely their codensity monads. This is the structure part of the structure{semantics adjunction for monads. However, the fact that not every functor has a codensity monad means that the structure functor is not defined on the category of all functors into the base category, but only on a full subcategory of it. This deficiency is solved when passing to general proto-theories with a canonical choice of aritation whose structure{semantics adjunction restricts to the usual one for monads. However, this comes at a cost: the semantics functor for general proto-theories is not full and faithful, unlike the one for monads. The condition that a semantics functor be full and faithful can be thought of as a kind of completeness theorem | it says that no information is lost when passing from a theory to its models. It is therefore desirable to retain this property of the semantics of monads if possible. The goal then, is to find a notion of algebraic theory that generalises monads for which the semantics functor is full and faithful with a left adjoint; equivalently the semantics functor should exhibit the category of theories as a re ective subcategory of the category of all functors into the base category. We achieve this (for well-behaved base categories) with a special kind of proto-theory enriched in topological spaces, which we call a complete topological proto-theory. We also pursue an analogy between the theory of proto-theories and that of groups. Under this analogy, monads correspond to finite groups, and complete topological proto-theories correspond to profinite groups. We give several characterisations of complete topological proto-theories in terms of monads, mirroring characterisations of profinite groups in terms of finite groups.

Es sei ein Heath-Jarrow-Morton Zinsstrukturmodell df(t,T) = alpha(t,T)dt + sigma(t,T)dX_t gegeben, angetrieben von einem mehrdimensionalen Semimartingal X. Das Ziel dieser Arbeit besteht darin, die Existenz endlich dimensionaler Realisierungen für solche Modelle zu untersuchen, wobei wir als treibende Prozesse die Klasse der Grigelionis Prozesse wählen, die insbesondere Levy Prozesse enthält. Zur Bearbeitung der Fragestellung werden zwei veschiedene Ansätze verfolgt. Wir dehnen die Ideen aus der Differenzialgeometrie von Björk und Svensson (2001) auf die vorliegende Situation aus und zeigen, dass das in der zitierten Arbeit bewiesene Kriterium für die Existenz endlich dimensionaler Realisierungen in unserem Fall als notwendiges Kriterium dienlich ist. Dieses Resultat wird auf konkrete Volatilitätsstrukturen angewandt. Im Kontext von sogenannten Benchmark Realisierungen, die eine natürliche Verallgemeinerung von Short Rate Realisierungen darstellen, leiten wir Integro-Differenzialgleichungen her, die für die Untersuchung der Existenz endlich dimensionaler Realisierungen hilfreich sind. Als Verallgemeinerung eines Resultats von Jeffrey (1995) beweisen wir außerdem, dass Zinsstrukturmodelle, die eine generische Benchmark Realisierung besitzen, notwendigerweise eine singuläre Hessesche Matrix haben. Beide Ansätze zeigen, dass neue Phänomene auftreten, sobald der treibende Prozess X Sprünge macht. Es gibt dann auf einmal nur noch sehr wenige Zinsstrukturmodelle, die endlich dimensionale Realisierungen zulassen, was ein beträchtlicher Unterschied zu solchen Modellen ist, die von einer Brownschen Bewegung angetrieben werden. Aus diesem Grund zeigen wir, dass für die in der Literatur oft behandelten Modelle mit deterministischer Richtungsvolatilität eine Folge von endlich dimensionalen Systemen existiert, die gegen das Zinsmodell konvergieren.
Let f(t,T) be a term structure model of Heath-Jarrow-Morton type df(t,T) = alpha(t,T)dt + sigma(t,T)dX_t, driven by a multidimensional semimartingale X. Our objective is to study the existence of finite dimensional realizations for equations of this kind. Choosing the class of Grigelionis processes (including in particular Levy processes) as driving processes, we approach this problem from two different directions. Extending the ideas from differential geometry in Björk and Svensson (2001), we show that the criterion for the existence of finite dimensional realizations, proven in the aforementioned paper, still serves as a necessary condition in our setup. This result is applied to concrete volatility structures. In the context of benchmark realizations, which are a natural generalization of short rate realizations, we derive integro-differential equations, suitable for the analysis of the realization problem. Generalizing Jeffrey (1995), we also prove a result stating that forward rate models, which generically possess a benchmark realization, must have a singular Hessian matrix. Both approaches reveal that, with regard to the results known for driving Wiener processes, new phenomena emerge, as soon as the driving process X has jumps. In particular, the occurrence of jumps severely limits the range of models that admit finite dimensional realizations. For this reason we prove, for the often considered case of deterministic direction volatility structures, the existence of finite dimensional systems converging to the forward rate model.

Apresentamos duas construções para unidades de uma ordem em uma classe de álgebras de quatérnios que é anel de divisão: as unidades de Pell e as unidades de Gauss. Classificamos os anéis de inteiros de extensões quadráticas racionais, $R$, cujo grupo de unidades $\\U (R G)$ é hiperbólico para um certo grupo $G$ fixado. Também classificamos os semigrupos finitos $S$, tal que, para a álgebra unitária $\\Q S$ e para toda $\\Z$-ordem $\\Gamma$ de $\\Q S$, o grupo de unidades $\\U (\\Gamma)$ é hiperbólico. Nesse mesmo contexto, classificamos os {\\it RA}-loops $L$ cujo loop de unidades $\\U (\\Z L)$ não contém um subgrupo abeliano livre de posto dois.
For a given division algebra of a quaternion algebra, we construct and define two types of units of its $\\Z$-orders: Pell units and Gauss units. Also, for the quadratic imaginary extensions over the racionals and some fixed group $G$, we classify the algebraic integral rings for which the unit group ring is a hyperbolic group. We also classify the finite semigroups $S$, for which all integral orders $\\Gamma$ of $\\Q S$ have hyperbolic unit group $\\U(\\Gamma)$. We conclude with the classification of the $RA$-loops $L$ for which the unit loop of its integral loop ring does not contain a free abelian subgroup of rank two.

La funzione di Möbius definita per insiemi parzialmente ordinati localmente finiti è un classico strumento di analisi combinatoria. Si tratta di una generalizzazione della funzione di Möbius nota in teoria dei numeri e ha varie applicazioni pure in teoria dei gruppi, dalla caratteristica di Eulero di complessi di sottogruppi fino allo studio di aspetti algebrici in automi cellulari. Nella prima parte della tesi richiamiamo alcune informazioni elementari per strutture d'ordine che sono legate alla funzione di Möbius, e ne presentiamo le principali proprietà, quali ad esempio la formula di inversione di Möbius e i teoremi di Crapo. Inoltre analizziamo alcuni legami importanti con argomenti di teoria dei gruppi, al fine di motivare il nostro interesse nei confronti della funzione di Möbius di gruppi lineari finiti. Nella seconda parte, lavoriamo su questi gruppi per studiarne la funzione di Möbius e otteniamo risultati originali che si rivelano utili per calcolarla, nota la struttura di alcuni particolari reticoli di sottospazi associati ai sottogruppi. Vediamo in dettaglio il caso in cui abbiamo un reticolo di sottospazi distributivo. In seguito mostriamo un esempio di sottogruppo del gruppo lineare generale, tale che il reticolo di sottospazi associato al sottogruppo non è distributivo. In questo modo osserviamo che i nostri ragionamenti hanno una validità più ampia e possono essere applicati a situazioni differenti, sotto determinate condizioni. Nell'ultima parte della tesi, colleghiamo i risultati ottenuti in precedenza ad alcune questioni aperte che riguardano gruppi profiniti finitamente generati e gruppi finiti almost-simple, presentando un approccio originale al problema. Benché poi questo problema non venga completamente risolto, otteniamo degli utili risultati parziali che possono essere sviluppati in futuro.
The Möbius function of locally finite partially ordered sets is a classical tool in enumerative combinatorics. It is a generalization of the number-theoretic Möbius function and it has several applications in group theory, from the Euler characteristic of subgroup complexes to algebraic aspects of cellular automata. In the first part of the thesis, we recall some basic notions about the order structures which are related to the Möbius function, and we present its main properties, such as the Möbius inversion formula and Crapo's theorems. Moreover, we investigate some relevant connections with group-theoretical topics to motivate our interest in the Möbius function of finite linear groups. In the second part, we work on these groups to obtain information about their Möbius function, and our original results are useful to compute it if we know the structure of some special subspace lattices related to subgroups. We study in detail the case of distributive subspace lattices. Then we show an example of a subgroup in the general linear group, such that the subspace lattice associated to the subgroup is non-distributive. In this way, we see that our arguments can also be applied to different situations, under certain conditions. In the last part of the thesis, we connect the previously obtained results to an open question about finitely generated profinite groups and finite almost-simple groups, introducing an original approach to the problem. Although we do not completely answer to this last question, we get some useful partial results.

Cette thèse, proposée dans le cadre du projet W2P1-DECOL (SAS PIVERT), financée par le ministère de l’enseignement supérieur est consacrée à l’étude d’un problème inverse de pressage des matériaux biologiques à structure cellulaire. Le but est d’identifier connaissant les mesures du flux d’huile sortant, le coefficient de consolidation du gâteau de pressage et l’inverse du temps caractéristique de consolidation sur deux niveaux : au niveau de la graine de colza et au niveau du gâteau de pressage. Dans un premier temps, nous présentons un système d’équations paraboliques modélisant le problème de pressage des matériaux biologiques à structure cellulaire, il découle de l’équation de continuité de la loi de Darcy et d’autres hypothèses simplificatrices. Puis l’analyse théorique et numérique du modèle direct est faite dans le cas linéaire. Enfin la méthode des différences finies est utilisée pour le discrétiser. Dans un second temps, nous introduisons le problème inverse du pressage où l’étude de l’identifiabilité de ce problème est résolue par une méthode spectrale. Par la suite, nous nous intéressons à l’étude de stabilité lipschitzienne locale et globale. De plus une estimation de stabilité lipschitzienne globale, pour le problème inverse de paramètres, dans le cas du système d’équations paraboliques, à partir des mesures sur ]0,T[ est établie. Enfin l’identification des paramètres est résolue par deux méthodes, l’une basée sur l’adaptation de la méthode algébrique et l’autre formulée comme la minimisation au sens des moindres carrés d’une fonctionnelle évaluant l’écart entre les mesures et les résultats du modèle direct, la résolution de ce problème inverse se fait en utilisant un algorithme itératif BFGS, l’algorithme est validé puis testé numériquement dans le cas des graines de colza, en utilisant des mesures synthétiques. Il donne des résultats très satisfaisants, malgré les difficultés rencontrés à manipuler et exploiter les données expérimentales
This thesis, proposed in the framework of the W2P1-DECOL project (SAS PIVERT) and funded by the Ministry of Higher Education, is devoted to the study an inverse problem of pressing biological materials with a cellular structure. The aim is to identify, of the outgoing oil flow, the coefficient of consolidation of the pressing cake and the inverse of the characteristic time of consolidation on two levels : at the level of the rapeseed and at the level of the pressing cake. First, we present a system of parabolic equations modeling the pressing problem of biological materials with cellular structure; it follows from the continuity equation of Darcy’s law and other simplifying hypotheses. Then a theoretical and numerical analysis of a direct model is made in the linear case. Finally the finite difference method is usedt o discretize it. In a second step, we introduce the inverse problem of the pressing where the study of the identifiability of this problem is solved by a spectral method. Later we are interested in the study of local and global Lipschitizian stability. Moreover, global Lipschitz stability estimate for the inverse problem of parameters in the case of the system of parabolic equations from the measures on ]0,T[ is established. Finally, the identification of the parameters is solved by two methods; one based on the adaptation of the algebraic method and the other formulated as the minimization in the least squares sense of a functional evaluating the difference between measurements and the results of the direct model; the resolution of this inverse problem is done using an iterative algorithm BFGS, the algorithm is validated and then tested numerically in the case of rapeseeds, using synthetic measures. It gives very satisfactory results, despite the difficulties encountered in handling and exploiting the experimental data

La prévention des risques industriels nécessite de simuler la dispersion turbulente de polluants. Cependant, les outils majoritairement utilisés à ce jour ne permettent pas de traiter les champs proches dans le cas de géométries complexes, et il est nécessaire d'utiliser les outils de CFD (“ Computational Fluid Dynamics ”) plus adaptés, mais plus coûteux. Afin de simuler les écoulements atmosphériques avec dispersion de polluants, les modèles CFD doivent modéliser correctement d'une part, les effets de flottabilité, et d'autre part les effets de la turbulence. Plusieurs approches existent, notamment dans la prise en compte des effets de flottabilité et la modélisation de la turbulence, et nécessitent des méthodes numériques adaptées aux spécificités mathématiques de chacune d'entre elles, ainsi que des schémas numériques précis pour ne pas polluer la modélisation. Une formulation d'ordre élevé en volumes finis, sur maillages non structurés, parallélisée, est proposée pour simuler les écoulements atmosphériques avec dispersion de polluants. L'utilisation de schémas d'ordre élevé doit permettre d'une part de réduire le nombre de cellules et diminuer les temps de simulation pour atteindre une précision donnée, et d'autre part de mieux contrôler la viscosité numérique des schémas en vue de simulations LES (Large Eddy Simulation), pour lesquelles la viscosité numérique des schémas peut masquer les effets de la modélisation. Deux schémas d'ordre élevé ont été étudiés et implémentés dans un solveur 3D Navier Stokes incompressible sur des maillages volumes finis non structurés. Nous avons développé un premier schéma d'ordre élevé, correspondant à un schéma Padé volumes finis, et nous avons étendu le schéma de reconstruction polynomiale de Carpentier (2000) aux écoulements incompressibles. Les propriétés numériques des différents schémas implémentés dans le même code de calcul sont étudiées sur différents cas tests bi-dimensionnels (calcul de flux convectifs et diffusifs sur une solution a-priori, convection d'une tâche gaussienne, décroissance d'un vortex de Taylor et cavité entraînée) et tri-dimensionnel (écoulement autour d'un obstacle cubique). Une attention particulière a été portée à l'étude de la précision et du traitement des conditions limites. L'implémentation proposée du schéma polynomial permet d'approcher, pour un maillage identique, les temps de simulation obtenus avec un schéma décentré classique d'ordre 2, mais avec une précision supérieure. Le schéma compact donne la meilleure précision. En utilisant une méthode de Jacobi sans calcul implicite de la matrice pour calculer le gradient, le temps de simulation devient intéressant uniquement lorsque la précision requise est importante. Une alternative est la résolution du système linéaire par une méthode multigrille algébrique. Cette méthode diminue considérablement le temps de calcul du gradient et le schéma Padé devient performant même pour des maillages grossiers. Enfin, pour réduire les temps de simulation, la parallélisation des schémas d'ordre élevé est réalisée par une décomposition en sous domaines. L'assemblage des flux s'effectue naturellement et différents solveurs proposés par les librairies PETSC et HYPRE (solveur multigrille algébrique et méthode de Krylov préconditionnée) permettent de résoudre les systèmes linéaires issus de notre problème. Le travail réalisé a consisté à identifier et déterminer les paramètres de résolution qui conduisent aux temps de simulation les plus faibles. Différents tests de speed-up et de scale-up ont permis de déterminer la méthode la plus efficace et ses paramètres optimaux pour la résolution en parallèle des systèmes linéaires issus de notre problème. Les résultats de ce travail ont fait l'objet d'une communication dans un congrès international “ parallel CFD juin 2008 ” et d'un article soumis à “ International Journal for Numerical Methods in Fluids ” (Analysis of high-order finite volume schemes for the incompressible Navier Stokes equations)

碩士
輔仁大學
數學系研究所
96
The idea of using estimation algebras to construct finite dimensional nonlinear filters was first proposed by Brockett and Mitter independently. It turns out that the concept of estimation algebra palys a crucial role in the investigation of finite dimensional nonlinear filters. In this thesis we apply the structure theorem for five-dimensional estimation algebras for a class of filtering systems to construct a special class of five-dimensional estimation algebras and hence a new class of finite dimensional filters.

Paper 1. This paper establishes several algebraic embedding theorems, each of which asserts that a certain kind of residuated structure can be embedded into a richer one. In almost all cases, the original structure has a compatible involution, which must be preserved by the embedding. The results, in conjunction with previous findings, yield separative axiomatizations of the deducibility relations of various substructural formal systems having double negation and contraposition axioms. The separation theorems go somewhat further than earlier ones in the literature, which either treated fewer subsignatures or focussed on the conservation of theorems only. Paper 2. It is proved that the variety of relevant disjunction lattices has the finite embeddability property (FEP). It follows that Avron’s relevance logic RMImin has a strong form of the finite model property, so it has a solvable deducibility problem. This strengthens Avron’s result that RMImin is decidable. Paper 3. An idempotent residuated po-monoid is semiconic if it is a subdirect product of algebras in which the monoid identity t is comparable with all other elements. It is proved that the quasivariety SCIP of all semiconic idempotent commutative residuated po-monoids is locally finite. The lattice-ordered members of this class form a variety SCIL, which is not locally finite, but it is proved that SCIL has the FEP. More generally, for every relative subvariety K of SCIP, the lattice-ordered members of K have the FEP. This gives a unified explanation of the strong finite model property for a range of logical systems. It is also proved that SCIL has continuously many semisimple subvarieties, and that the involutive algebras in SCIL are subdirect products of chains. Paper 4. Anderson and Belnap’s implicational system RMO can be extended conservatively by the usual axioms for fusion and for the Ackermann truth constant t. The resulting system RMO is algebraized by the quasivariety IP of all idempotent commutative residuated po-monoids. Thus, the axiomatic extensions of RMO are in one-to-one correspondence with the relative subvarieties of IP. It is proved here that a relative subvariety of IP consists of semiconic algebras if and only if it satisfies x (x t) x. Since the semiconic algebras in IP are locally finite, it follows that when an axiomatic extension of RMO has ((p t) p) p among its theorems, then it is locally tabular. In particular, such an extension is strongly decidable, provided that it is finitely axiomatized.
Thesis (Ph.D.)-University of KwaZulu-Natal, Westville, 2008.

This study investigates the possibilities and implications for the teaching of the solving of polynomial equations. It is historically directed and also focusses on the working procedures in algebra which target the cognitive and affective domains. The teaching implications of the development of representational styles of equations and their solving procedures are noted. Since concepts in algebra can be conceived as processes or objects this leads to cognitive obstacles, for example: a limited view of the equal sign, which result in learning and reasoning problems. The roles of sense-making, visual imagery, mental schemata and networks in promoting meaningful understanding are scrutinised. Questions and problems to solve are formulated to promote the processes associated with the solving of polynomial equations, and the solving procedures used by a group of college students are analysed. A teaching model/method, which targets the cognitive and affective domains, is presented.
Mathematics Education
M.A. (Mathematics Education)