An R package for permutations, Mallows and Generalized Mallows models

[EN]Probability models on permutations associate a probability value to each of the permutations on n items. This paper considers two popular probability models, the Mallows model and the Generalized Mallows model. We describe methods for making inference, sampling and learning such distributions, some of which are novel in the literature. This paper also describes operations for permutations, with special attention in those related with the Kendall and Cayley distances and the random generation of permutations. These operations are of key importance for the efficient computation of the operations on distributions. These algorithms are implemented in the associated R package. Moreover, the internal code is written in C++.

Geometric multiplicity margin for a submatrix

AMS Classification: 15A18, 15A21, 15A60.

Extending Distance-based Ranking Models In Estimation of Distribution Algorithms

Recently, probability models on rankings have been proposed in the field of estimation of distribution algorithms in order to solve permutation-based combinatorial optimisation problems. Particularly, distance-based ranking models, such as Mallows and Generalized Mallows under the Kendall’s-t distance, have demonstrated their validity when solving this type of problems. Nevertheless, there are still many trends that deserve further study. In this paper, we extend the use of distance-based ranking models in the framework of EDAs by introducing new distance metrics such as Cayley and Ulam. In order to analyse the performance of the Mallows and Generalized Mallows EDAs under the Kendall, Cayley and Ulam distances, we run them on a benchmark of 120 instances from four well known permutation problems. The conducted experiments showed that there is not just one metric that performs the best in all the problems. However, the statistical test pointed out that Mallows-Ulam EDA is the most stable algorithm among the studied proposals.

Descriptive set theory and the ergodic theory of countable groups

The primary focus of this thesis is on the interplay of descriptive set theory and the ergodic theory of group actions. This incorporates the study of turbulence and Borel reducibility on the one hand, and the theory of orbit equivalence and weak equivalence on the other. Chapter 2 is joint work with Clinton Conley and Alexander Kechris; we study measurable graph combinatorial invariants of group actions and employ the ultraproduct construction as a way of constructing various measure preserving actions with desirable properties. Chapter 3 is joint work with Lewis Bowen; we study the property MD of residually finite groups, and we prove a conjecture of Kechris by showing that under general hypotheses property MD is inherited by a group from one of its co-amenable subgroups. Chapter 4 is a study of weak equivalence. One of the main results answers a question of Abért and Elek by showing that within any free weak equivalence class the isomorphism relation does not admit classification by countable structures. The proof relies on affirming a conjecture of Ioana by showing that the product of a free action with a Bernoulli shift is weakly equivalent to the original action. Chapter 5 studies the relationship between mixing and freeness properties of measure preserving actions. Chapter 6 studies how approximation properties of ergodic actions and unitary representations are reflected group theoretically and also operator algebraically via a group's reduced C^*-algebra. Chapter 7 is an appendix which includes various results on mixing via filters and on Gaussian actions.

Ordinary mod p representations of the metaplectic cover of p-adic SL_2

We classify the genuine ordinary mod p representations of the metaplectic group SL(2,F)-tilde, where F is a p-adic field, and compute its genuine mod p spherical and Iwahori Hecke algebras. The motivation is an interest in a possible correspondence between genuine mod p representations of SL(2,F)-tilde and mod p representations of the dual group PGL(2,F), so we also compare the two Hecke algebras to the mod p spherical and Iwahori Hecke algebras of PGL(2,F). We show that the genuine mod p spherical Hecke algebra of SL(2,F)-tilde is isomorphic to the mod p spherical Hecke algebra of PGL(2,F), and that one can choose an isomorphism which is compatible with a natural, though partial, correspondence of unramified ordinary representations via the Hecke action on their spherical vectors. We then show that the genuine mod p Iwahori Hecke algebra of SL(2,F)-tilde is a subquotient of the mod p Iwahori Hecke algebra of PGL(2,F), but that the two algebras are not isomorphic. This is in contrast to the situation in characteristic 0, where by work of Savin one can recover the local Shimura correspondence for representations generated by their Iwahori fixed vectors from an isomorphism of Iwahori Hecke algebras.

Ortho-positronium annihilation: steps toward computing the first order radiative corrections

The 0.2% experimental accuracy of the 1968 Beers and Hughes measurement of the annihilation lifetime of ortho-positronium motivates the attempt to compute the first order quantum electrodynamic corrections to this lifetime. The theoretical problems arising in this computation are here studied in detail up to the point of preparing the necessary computer programs and using them to carry out some of the less demanding steps -- but the computation has not yet been completed. Analytic evaluation of the contributing Feynman diagrams is superior to numerical evaluation, and for this process can be carried out with the aid of the Reduce algebra manipulation computer program.

The relation of the positronium decay rate to the electronpositron annihilation-in-flight amplitude is derived in detail, and it is shown that at threshold annihilation-in-flight, Coulomb divergences appear while infrared divergences vanish. The threshold Coulomb divergences in the amplitude cancel against like divergences in the modulating continuum wave function.

Using the lowest order diagrams of electron-positron annihilation into three photons as a test case, various pitfalls of computer algebraic manipulation are discussed along with ways of avoiding them. The computer manipulation of artificial polynomial expressions is preferable to the direct treatment of rational expressions, even though redundant variables may have to be introduced.

Special properties of the contributing Feynman diagrams are discussed, including the need to restore gauge invariance to the sum of the virtual photon-photon scattering box diagrams by means of a finite subtraction.

A systematic approach to the Feynman-Brown method of Decomposition of single loop diagram integrals with spin-related tensor numerators is developed in detail. This approach allows the Feynman-Brown method to be straightforwardly programmed in the Reduce algebra manipulation language.

The fundamental integrals needed in the wake of the application of the Feynman-Brown decomposition are exhibited and the methods which were used to evaluate them -- primarily dis persion techniques are briefly discussed.

Finally, it is pointed out that while the techniques discussed have permitted the computation of a fair number of the simpler integrals and diagrams contributing to the first order correction of the ortho-positronium annihilation rate, further progress with the more complicated diagrams and with the evaluation of traces is heavily contingent on obtaining access to adequate computer time and core capacity.

Modelando evolução por endossimbiose

Nesta dissertação é apresentada uma modelagem analítica para o processo evolucionário formulado pela Teoria da Evolução por Endossimbiose representado através de uma sucessão de estágios envolvendo diferentes interações ecológicas e metábolicas entre populações de bactérias considerando tanto a dinâmica populacional como os processos produtivos dessas populações. Para tal abordagem é feito uso do sistema de equações diferenciais conhecido como sistema de Volterra-Hamilton bem como de determinados conceitos geométricos envolvendo a Teoria KCC e a Geometria Projetiva. Os principais cálculos foram realizados pelo pacote de programação algébrica FINSLER, aplicado sobre o MAPLE.

Some constructions, related to noncommutative tori; Fredholm modules and the Beilinson-Bloch regulator

A noncommutative 2-torus is one of the main toy models of noncommutative geometry, and a noncommutative n-torus is a straightforward generalization of it. In 1980, Pimsner and Voiculescu in [17] described a 6-term exact sequence, which allows for the computation of the K-theory of noncommutative tori. It follows that both even and odd K-groups of n-dimensional noncommutative tori are free abelian groups on 2^n-1 generators. In 1981, the Powers-Rieffel projector was described [19], which, together with the class of identity, generates the even K-theory of noncommutative 2-tori. In 1984, Elliott [10] computed trace and Chern character on these K-groups. According to Rieffel [20], the odd K-theory of a noncommutative n-torus coincides with the group of connected components of the elements of the algebra. In particular, generators of K-theory can be chosen to be invertible elements of the algebra. In Chapter 1, we derive an explicit formula for the First nontrivial generator of the odd K-theory of noncommutative tori. This gives the full set of generators for the odd K-theory of noncommutative 3-tori and 4-tori.

In Chapter 2, we apply the graded-commutative framework of differential geometry to the polynomial subalgebra of the noncommutative torus algebra. We use the framework of differential geometry described in [27], [14], [25], [26]. In order to apply this framework to noncommutative torus, the notion of the graded-commutative algebra has to be generalized: the "signs" should be allowed to take values in U(1), rather than just {-1,1}. Such generalization is well-known (see, e.g., [8] in the context of linear algebra). We reformulate relevant results of [27], [14], [25], [26] using this extended notion of sign. We show how this framework can be used to construct differential operators, differential forms, and jet spaces on noncommutative tori. Then, we compare the constructed differential forms to the ones, obtained from the spectral triple of the noncommutative torus. Sections 2.1-2.3 recall the basic notions from [27], [14], [25], [26], with the required change of the notion of "sign". In Section 2.4, we apply these notions to the polynomial subalgebra of the noncommutative torus algebra. This polynomial subalgebra is similar to a free graded-commutative algebra. We show that, when restricted to the polynomial subalgebra, Connes construction of differential forms gives the same answer as the one obtained from the graded-commutative differential geometry. One may try to extend these notions to the smooth noncommutative torus algebra, but this was not done in this work.

A reconstruction of the Beilinson-Bloch regulator (for curves) via Fredholm modules was given by Eugene Ha in [12]. However, the proof in [12] contains a critical gap; in Chapter 3, we close this gap. More specifically, we do this by obtaining some technical results, and by proving Property 4 of Section 3.7 (see Theorem 3.9.4), which implies that such reformulation is, indeed, possible. The main motivation for this reformulation is the longer-term goal of finding possible analogs of the second K-group (in the context of algebraic geometry and K-theory of rings) and of the regulators for noncommutative spaces. This work should be seen as a necessary preliminary step for that purpose.

For the convenience of the reader, we also give a short description of the results from [12], as well as some background material on central extensions and Connes-Karoubi character.

Free algebras in Von Neumann-Bernays-Gӧdel set theory and positive elementary inductions in reasonable structures

This thesis consists of two independent chapters. The first chapter deals with universal algebra. It is shown, in von Neumann-Bernays-Gӧdel set theory, that free images of partial algebras exist in arbitrary varieties. It follows from this, as set-complete Boolean algebras form a variety, that there exist free set-complete Boolean algebras on any class of generators. This appears to contradict a well-known result of A. Hales and H. Gaifman, stating that there is no complete Boolean algebra on any infinite set of generators. However, it does not, as the algebras constructed in this chapter are allowed to be proper classes. The second chapter deals with positive elementary inductions. It is shown that, in any reasonable structure ᶆ, the inductive closure ordinal of ᶆ is admissible, by showing it is equal to an ordinal measuring the saturation of ᶆ. This is also used to show that non-recursively saturated models of the theories ACF, RCF, and DCF have inductive closure ordinals greater than _ω.

Special Frobenius Traces in Galois Representations

This thesis studies Frobenius traces in Galois representations from two different directions. In the first problem we explore how often they vanish in Artin-type representations. We give an upper bound for the density of the set of vanishing Frobenius traces in terms of the multiplicities of the irreducible components of the adjoint representation. Towards that, we construct an infinite family of representations of finite groups with an irreducible adjoint action.

In the second problem we partially extend for Hilbert modular forms a result of Coleman and Edixhoven that the Hecke eigenvalues a_p of classical elliptical modular newforms f of weight 2 are never extremal, i.e., a_p is strictly less than 2[square root]p. The generalization currently applies only to prime ideals p of degree one, though we expect it to hold for p of any odd degree. However, an even degree prime can be extremal for f. We prove our result in each of the following instances: when one can move to a Shimura curve defined by a quaternion algebra, when f is a CM form, when the crystalline Frobenius is semi-simple, and when the strong Tate conjecture holds for a product of two Hilbert modular surfaces (or quaternionic Shimura surfaces) over a finite field.

Optical intrinsically fuzzy mathematical morphology for gray-scale image processing

Intrinsically fuzzy morphological erosion and dilation are extended to a total of eight operations that have been formulated in terms of a single morphological operation--biased dilation. Based on the spatial coding of a fuzzy variable, a bidirectional projection concept is proposed. Thus, fuzzy logic operations, arithmetic operations, gray-scale dilation, and erosion for the extended intrinsically fuzzy morphological operations can be included in a unified algorithm with only biased dilation and fuzzy logic operations. To execute this image algebra approach we present a cellular two-layer processing architecture that consists of a biased dilation processor and a fuzzy logic processor. (C) 1996 Optical Society of America

Logic-operated mathematical morphology and its optical implementation

A more powerful tool for binary image processing, i.e., logic-operated mathematical morphology (LOMM), is proposed. With LOMM the image and the structuring element (SE) are treated as binary logical variables, and the MULTIPLY between the image and the SE in correlation is replaced with 16 logical operations. A total of 12 LOMM operations are obtained. The optical implementation of LOMM is described. The application of LOMM and its experimental results are also presented. (C) 1999 Optical Society of America.

FUZZY SOLID SETS FOR MATHEMATICAL MORPHOLOGY AND OPTICAL IMPLEMENTATION

Fuzzy sets in the subject space are transformed to fuzzy solid sets in an increased object space on the basis of the development of the local umbra concept. Further, a counting transform is defined for reconstructing the fuzzy sets from the fuzzy solid sets, and the dilation and erosion operators in mathematical morphology are redefined in the fuzzy solid-set space. The algebraic structures of fuzzy solid sets can lead not only to fuzzy logic but also to arithmetic operations. Thus a fuzzy solid-set image algebra of two image transforms and five set operators is defined that can formulate binary and gray-scale morphological image-processing functions consisting of dilation, erosion, intersection, union, complement, addition, subtraction, and reflection in a unified form. A cellular set-logic array architecture is suggested for executing this image algebra. The optical implementation of the architecture, based on area coding of gray-scale values, is demonstrated. (C) 1995 Optical Society of America

Morphological ordered gray-scale erosion for optical image processing

An ordered gray-scale erosion is suggested according to the definition of hit-miss transform. Instead of using three operations, two images, and two structuring elements, the developed operation requires only one operation and one structuring element, but with three gray-scale levels. Therefore, a union of the ordered gray-scale erosions with different structuring elements can constitute a simple image algebra to program any combined image processing function. An optical parallel ordered gray-scale erosion processor is developed based on the incoherent correlation in a single channel. Experimental results are also given for an edge detection and a pattern recognition. (C) 1998 Society of Photo-Optical Instrumentation Engineers. [S0091-3286(98)00306-7].

Stationary random response of multidegree-of-freedom systems

An approximate approach is presented for determining the stationary random response of a general multidegree-of-freedom nonlinear system under stationary Gaussian excitation. This approach relies on defining an equivalent linear system for the nonlinear system. Two particular systems which possess exact solutions have been solved by this approach, and it is concluded that this approach can generate reasonable solutions even for systems with fairly large nonlinearities. The approximate approach has also been applied to two examples for which no exact or approximate solutions were previously available.

Also presented is a matrix algebra approach for determining the stationary random response of a general multidegree-of-freedom linear system. Its derivation involves only matrix algebra and some properties of the instantaneous correlation matricies of a stationary process. It is therefore very direct and straightforward. The application of this matrix algebra approach is in general simpler than that of commonly used approaches.