Academic literature on the topic 'Lattice quotients'

AbstractOrdering permutations by containment of inversion sets yields a fascinating partial order on the symmetric group: the weak order. This partial order is, among other things, a semidistributive lattice. As a consequence, every permutation has a canonical representation as a join of other permutations. Combinatorially, these canonical join representations can be modeled in terms of arc diagrams. Moreover, these arc diagrams also serve as a model to understand quotient lattices of the weak order. A particularly well-behaved quotient lattice of the weak order is the well-known Tamari lattice, which appears in many seemingly unrelated areas of mathematics. The arc diagrams representing the members of the Tamari lattices are better known as noncrossing partitions. Recently, the Tamari lattices were generalized to parabolic quotients of the symmetric group. In this article, we undertake a structural investigation of these parabolic Tamari lattices, and explain how modified arc diagrams aid the understanding of these lattices.

We study the quadratic quotients of the incidence category of the Young lattice defined by the zero relations corresponding to adding two boxes to the same row, or to the same column, or both. We show that the last quotient corresponds to the Koszul dual of the original incidence category, while the first two quotients are, in a natural way, Koszul duals of each other and hence they are in particular Koszul self-dual. Both of these two quotients are known to be basic representatives in the Morita equivalence class of the category of injections between finite sets. We also present a new, rather direct, argument establishing this Morita equivalence.

Frame theory is the study of topology based on its open set lattice, and it was studied extensively by various authors. In this paper, we study quotients of intuitionistic fuzzy filters of an intuitionistic fuzzy coframe. The quotients of intuitionistic fuzzy filters are shown to be filters of the given intuitionistic fuzzy coframe. It is shown that the collection of all intuitionistic fuzzy filters of a coframe and the collection of all intutionistic fuzzy quotient filters of an intuitionistic fuzzy filter are coframes.

In this work, we consider the existence and construction of pseudocomplements in some lattices of module classes. The classes of modules belonging to these lattices are defined via closure under operations such as taking submodules, quotients, extensions, injective hulls, direct sums or products. We characterize the rings for which the lattices [Formula: see text]-tors (of hereditary torsion classes), [Formula: see text]-nat (the lattice of natural classes) and [Formula: see text]-conat (the lattice of conatural classes) coincide.

LetEbe a Banach lattice and letMbe a norm-closed and Dedekindσ-complete ideal ofE. IfEcontains a lattice-isometric copy ofℓ∞, thenE/Mcontains such a copy as well, orMcontains a lattice copy ofℓ∞. This is one of the consequences of more general results presented in this paper.

The aim of this paper is to establish a lattice theoretical framework to study the partially ordered set t o r s A \mathsf {tors} A of torsion classes over a finite-dimensional algebra A A . We show that t o r s A \mathsf {tors} A is a complete lattice which enjoys very strong properties, as bialgebraicity and complete semidistributivity. Thus its Hasse quiver carries the important part of its structure, and we introduce the brick labelling of its Hasse quiver and use it to study lattice congruences of t o r s A \mathsf {tors} A . In particular, we give a representation-theoretical interpretation of the so-called forcing order, and we prove that t o r s A \mathsf {tors} A is completely congruence uniform. When I I is a two-sided ideal of A A , t o r s ( A / I ) \mathsf {tors} (A/I) is a lattice quotient of t o r s A \mathsf {tors} A which is called an algebraic quotient, and the corresponding lattice congruence is called an algebraic congruence. The second part of this paper consists in studying algebraic congruences. We characterize the arrows of the Hasse quiver of t o r s A \mathsf {tors} A that are contracted by an algebraic congruence in terms of the brick labelling. In the third part, we study in detail the case of preprojective algebras Π \Pi , for which t o r s Π \mathsf {tors} \Pi is the Weyl group endowed with the weak order. In particular, we give a new, more representation theoretical proof of the isomorphism between t o r s k Q \mathsf {tors} k Q and the Cambrian lattice when Q Q is a Dynkin quiver. We also prove that, in type A A , the algebraic quotients of t o r s Π \mathsf {tors} \Pi are exactly its Hasse-regular lattice quotients.

We give necessary and sufficient conditions for nuclearity of Cuntz–Nica–Pimsner algebras for a variety of quasi-lattice ordered groups. First we deal with the free abelian lattice case. We use this as a stepping-stone to tackle product systems over quasi-lattices that are controlled by the free abelian lattice and satisfy a minimality property. Our setting accommodates examples like the Baumslag–Solitar lattice for $n=m>0$ and the right-angled Artin groups. More generally, the class of quasi-lattices for which our results apply is closed under taking semi-direct and graph products. In the process we accomplish more. Our arguments tackle Nica–Pimsner algebras that admit a faithful conditional expectation on a small fixed point algebra and a faithful copy of the coefficient algebra. This is the case for CNP-relative quotients in-between the Toeplitz–Nica–Pimsner algebra and the Cuntz–Nica–Pimsner algebra. We complete this study with the relevant results on exactness.

En combinatoire algébrique, les treillis sont des ensembles partiellement ordonnés qui possèdent à la fois des opérations inf et sup. L'ordre faible sur les permutations est un exemple classique de treillis qui possède une riche structure combinatoire. Cela en a fait un point de départ à partir duquel d'autres objets combinatoires ont été définis. Pour cette thèse, nous nous concentrons sur l'étude de deux familles différentes de treillis en relation avec l'ordre faible: les treillis des permusylvestres et le s-ordre faible. La première partie de la thèse concerne la théorie des quotients de treillis de l'ordre faible en s'appuyant sur le travail de N. Reading. On se concentre spécifiquement sur la famille des quotients des permusylvestres de l'ordre faible. En les considérant comme des permusylvestres, comme dans le travail de V. Pilaud et V. Pons, nous étendons la technologie des vecteurs de crochet des arbres binaires en définissant les vecteurs d'inversion et les vecteurs cubiques. Le vecteur d'inversion capture l'opération de meet de ces treillis tandis que le vecteur cubique permet de les réaliser géométriquement via une configuration cubique. En changeant de point de vue et en étudiant ces quotients à travers les éléments minimaux de leurs classes de congruence, nous utilisons la description de Coxeter de type A des permutations pour caractériser les permusylvestres avec l'aide d'automates. Ces automates capturent l'évitement de motifs ijk et/ou kij impliqués par ces quotients et nous permettent de définir des algorithmes qui généralisent le tri par pile. Dans le cas où le quotient correspond à un treillis cambrien, nous relions nos automates au tri de Coxeter. Nous donnons quelques indications sur le même phénomène pour les groupes de Coxeter de types B et D. La deuxième partie de cette thèse découle du travail de V. Pons et C. Ceballos qui ont défini le s-ordre faible sur les arbres s-décroissants où s est une séquence d'entiers positifs. Dans le cas de s=(1,ldots,1), cette définition récupère l'ordre faible. Dans leur premier article, les auteurs ont conjecturé que le s-permutaèdre pouvait être réalisé dans l'espace comme une subdivision polyédrique d'un zonotope. Nous donnons une réponse positive à leur conjecture lorsque s est une séquence d'entiers positifs en définissant un graphe dont les polytopes de flot nous permettent de récupérer le s-ordre faible. Nous utilisons des techniques de flots sur les graphes, de géométrie discrète et de géométrie tropicale pour obtenir des réalisations du s-permutaèdre avec différentes propriétés. Avec l'idée de décrire les quotients de treillis de le s-ordre faible, nous étudions leurs éléments sup-irréductibles. Nous introduisons également une opération sur les graphes pour définir un analogue des quotients de treillis des permusylvestres sur ces treillis
In algebraic combinatorics, lattices are partially ordered sets which possess both meet and join operations. The weak order on permutations is a classical example of a lattice that has a rich combinatorial structure. This has made it a starting point from which other combinatorial objects have been defined. For this thesis, we focus on studying two different families of lattices in relation to the weak order: the permutree lattices and the s-weak order. The first part of the thesis involves the theory of lattice quotients of the weak order building upon the work of N. Reading, specifically focusing on the family of permutree quotients of the weak order. Considering them as permutrees, as done by V. Pilaud and V. Pons, we extend the technology of bracket vectors from binary trees by defining inversion and cubic vectors. The inversion vector captures the meet operation of these lattices while the cubic vector helps realizes them geometrically via a cubical configuration. Changing our point of view and studying these quotients through the minimal elements of their congruence classes, we use the Coxeter Type A description of permutations to characterize permutrees using automata. These automata capture the pattern avoidance of ijk and/or kij implied by these quotients and allow us to define algorithms which generalize stack sorting. In the case where the quotient corresponds to a Cambrian lattice we relate our automata with Coxeter sorting. We give some insight about the same phenomenon for Coxeter groups of types B and D. The second part of this thesis stems from the work of V. Pons and C. Ceballos who defined the s-weak order on s-decreasing trees where s is a sequence of non-negative integers. In the case of s=(1,ldots,1) this definition recovers the weak order. In their first article, the authors conjectured that the s-permutahedron could be realized in space as a polyhedral subdivision of a zonotope. We give a positive answer to their conjecture when s is a sequence of positive integers by defining a graph whose flow polytopes allows us to recover the s-weak order. We use techniques from flows on graphs, discrete geometry, and tropical geometry to obtain realizations of the s-permutahedron with different properties. With the idea of describing the lattice quotients of the s-weak order, we study their join-irreducibles. We introduce as well a graph operation to define an analog of permutree quotients on these lattices

We study various quotient maps between frames which are defined by stipulating that they satisfy certain conditions on the cozero parts of their domains and codomains. By way of example, we mention that C-quotient and C -quotient maps (as defined by Ball and Walters- Wayland [7]) are typical of the types of homomorphisms we consider in the initial parts of the thesis. To be little more precise, we study uplifting quotient maps, C1- and C2-quotient maps and show that these quotient maps possess some properties akin to those of a C-quotient maps. The study also focuses on R - and G - quotient maps and show, amongst other things, that these quotient maps coincide with the well known C - quotient maps in mildly normal frames. We also study quasi-F frames and give a ring-theoretic characterization that L is quasi-F precisely when the ring RL is quasi-B´ezout. We also show that quasi-F frames are preserved and reflected by dense coz-onto R -quotient maps. We characterize normality and some of its weaker forms in terms of some of these quotient maps. Normality is characterized in terms of uplifting quotient maps, -normally separated frames in terms of C1-quotient maps and mild normality in terms of R - and G -quotient maps. Finally we define cozero complemented frames and show that they are preserved and reflected by dense z#- quotient maps. We end by giving ring-theoretic characterizations of these frames.
Mathematical Science
D. Phil. (Mathematics)

Extending an explicit result from Bridson–Conder–Reid, this work provides an algorithm for distinguishing finite quotients between cocompact triangle groups Δ ?and lattices Γ of constant curvature symmetric 2-spaces. Much of our attention will be on when these lattices are Fuchsian groups. We prove that it will suffice to take a finite quotient that is Abelian, dihedral, a subgroup of PSL(n,F_q) (for an odd prime power q), or an Abelian extension of one of these 3 groups. For the latter case, we will require and develop an approach for creating group extensions upon a shared finite quotient of Δ? and Γ which between them have differing degrees of smoothness. Furthermore, on the order of a finite quotient that distinguishes between ?Δ and Γ, we are able to establish an effective upperbound that is superexponential depending on the cone orders appearing in each group.

This book is devoted to a general study of geometric theories from a topos-theoretic perspective. After recalling the necessary topos-theoretic preliminaries, it presents the main methodology it uses to extract ‘concrete’ information on theories from properties of their classifying toposes—the ‘bridge’ technique. As a first implementation of this methodology, a duality is established between the subtoposes of the classifying topos of a geometric theory and the geometric theory extensions (also called ‘quotients’) of the theory. Many concepts of elementary topos theory which apply to the lattice of subtoposes of a given topos are then transferred via this duality into the context of geometric theories. A second very general implementation of the ‘bridge’ technique is the investigation of the class of theories of presheaf type (i.e. classified by a presheaf topos). After establishing a number of preliminary results on flat functors in relation to classifying toposes, the book carries out a systematic investigation of this class resulting in a number of general results and a characterization theorem allowing one to test whether a given theory is of presheaf type by considering its models in arbitrary Grothendieck toposes. Expansions of geometric theories and faithful interpretations of theories of presheaf type are also investigated. As geometric theories can always be written (in many ways) as quotients of presheaf type theories, the study of quotients of a given theory of presheaf type is undertaken. Lastly, the book presents a number of applications in different fields of mathematics of the theory it develops.

This chapter deals with two related problems occurring frequently in the physical sciences: first, the problem of estimating the value of a function from a limited number of data points; and second, the problem of calculating its value from a series approximation. Numerical methods for interpolating and extrapolating data are presented. The famous Lagrange interpolating polynomial is introduced and applied to one-dimensional and multidimensional problems. Cubic spline interpolation is introduced and an implementation in terms of Eigen classes is given. Several techniques for improving the convergence of Taylor series are discussed, including Shank’s transformation, Richardson extrapolation, and the use of Padé approximants. Conversion between representations with the quotient-difference algorithm is discussed. The exercises explore public transportation, human vision, the wine market, and SU(2) lattice gauge theory, among other topics.

AbstractCyclic lattices and ideal lattices were introduced by Micciancio in [45], Lyubashevsky and Micciancio in [40], respectively, which play an efficient role in Ajtai’s construction of a collision-resistant Hash function and in Gentry’s construction of fully homomorphic encryption [22]. Let $$R=\mathbb {Z}[x]/<\phi (x)>$$ be a quotient ring of the integer coefficients polynomials ring, Lyubashevsky and Micciancio regarded an ideal lattice as the correspondence of an ideal of R, but they neither explain how to extend this definition to whole Euclidean space $$\mathbb {R}^n$$, nor exhibit the relationship of cyclic lattices and ideal lattices. In this chapter, we regard the cyclic lattices and ideal lattices as the correspondences of finitely generated R-modules, so that we may show that ideal lattices are actually a special subclass of cyclic lattices, namely cyclic integer lattices. It is worth noting that we use more general rotation matrix here, so our definition and results on cyclic lattices and ideal lattices are more general forms. As application, we provide cyclic lattice with an explicit and countable upper bound for the smoothing parameter. Our results may be viewed as a substantial progress in this direction.

AbstractCyclic lattices and ideal lattices were introduced by Micciancio (2002), Lyubashevsky and Micciancio (2006), respectively, which play an efficient role in Ajtai’s construction of a collision resistant Hash function (see Ajtai (1996), Ajtai and Dwork (1997)) and in Gentry’s construction of fully homomorphic encryption (see Gentry (2009)). Let $$R=Z[x]/\langle \phi (x)\rangle $$ R = Z [ x ] / ⟨ ϕ ( x ) ⟩ be a quotient ring of the integer coefficients polynomials ring, Lyubashevsky and Micciancio regarded an ideal lattice as the correspondence of an ideal of R, but they neither explain how to extend this definition to whole Euclidean space $$\mathbb {R}^n$$ R n , nor exhibit the relationship of cyclic lattices and ideal lattices. In this chapter, we regard the cyclic lattices and ideal lattices as the correspondences of finitely generated R-modules, so that we may show that ideal lattices are actually a special subclass of cyclic lattices, namely, cyclic integer lattices. In fact, there is a one to one correspondence between cyclic lattices in $$\mathbb {R}^n$$ R n and finitely generated R-modules (see Theorem 4). On the other hand, since R is a Noether ring, each ideal of R is a finitely generated R-module, so it is natural and reasonable to regard ideal lattices as a special subclass of cyclic lattices (see Corollary 7). It is worth noting that we use a more general rotation matrix here, so our definition and results on cyclic lattices and ideal lattices are more general forms. As an application, we provide a cyclic lattice with an explicit and countable upper bound for the smoothing parameter (see Theorem 5). It is an open problem that is the shortest vector problem on cyclic lattice NP-hard (see Micciancio (2002)). Our results may be viewed as a substantial progress in this direction.

In this chapter, the aim is to discuss computational aspects of lattice-based cryptographic schemes focused on NTRU in view of the time complexity on a graphical processing unit (GPU). Polynomial multiplication algorithms, having a very important role in lattice-based cryptographic schemes, are implemented on the GPU using the compute unified device architecture (CUDA) platform. They are implemented in both serial and parallel way. Compact and efficient implementation architectures of polynomial multiplication for lattice-based cryptographic schemes are presented for the quotient ring both Zp [x]/(xn-1) and Zp [x]/(xn+1), where p is a prime number. Then, by using these implementations the NTRUEncrypt and signature scheme working over Zp [x]/(xn+1) are implemented on the GPU using CUDA platform. Implementation details are also discussed.