Álgebra
https://hdl.handle.net/11441/10803
Fri, 20 Sep 2019 03:07:59 GMT2019-09-20T03:07:59ZQuantum álgorithms for the combinatorial invariants of numerical semigroups
https://hdl.handle.net/11441/87264
Quantum álgorithms for the combinatorial invariants of numerical semigroups
It was back in spring 2014 when the author of this doctoral dissertation was
finishing its master thesis, whose main objective was the understanding of
Peter W. Shor’s most praised result, a quantum algorithm capable of
factoring integers in polynomial time. During the development of this master
thesis, me and my yet-tobe doctoral advisor studied the main aspects of
quantum computing from a purely algebraic perspective. This research
eventually evolved into a sufficiently thorough canvas capable of explaining
the main aspects and features of the mentioned algorithm from within an
undergraduate context.
Just after its conclusion, we seated down and elaborated a research plan for
a future Ph.D. thesis, which would expectantly involve quantum computing but
also a branch of algebra whose apparently innocent definitions hide some
really hard problems from a computational perspective: the theory of
numerical semigroups. As will be seen later, the definition of numerical
semigroup does not involve sophisticated knowledge from any somewhat obscure
and distant branch of the tree of mathematics. Nonetheless, a number of
combinatorial problems associated with these numerical semigroups are
extremely hard to solve, even when the size of the input is relatively
small. Some examples of these problems are the calculations of the Frobenius
number, the Apéry set, and the Sylvester denumerant, all of them bearing the
name of legendary mathematicians.
This thesis is the result of our multiple attempts to tackle those
combinatorial problems with the help of a hypothetical quantum computer.
First, Chapter 2 is devoted to numerical semigroups and computational
complexity theory, and is divided into three sections. In Section 2.1, we
give the formal definition of a numerical semigroup, along with a
description of the main problems involved with them. In Section 2.2, we
sketch the fundamental concepts of complexity theory, in order to understand
the true significance within the inherent hardness concealed in the
resolution of those problems. Finally, in Section 2.3 we prove the
computational complexity of the problems we aim to solve.
Chapter 3 is the result of our outline of the theory of quantum computing.
We give the basic definitions and concepts needed for understanding the
particular place that quantum computers occupy in the world of Turing
machines, and also the main elements that compose this particular model of
computation: quantum bits and quantum entanglement. We also explain the two
most common models of quantum computation, namely quantum circuits and
adiabatic quantum computers. For all of them we give mathematical
definitions, but always having in mind the physical experiments from which
they stemmed.
Chapter 4 is also about quantum computing, but from an algorithmical
perspective. We present the most important quantum algorithms to date in a
standardized way, explaining their context, their impact and consequences,
while giving a mathematical proof of their correctness and worked-out
examples. We begin with the early algorithms of Deutsch, Deutsch-Jozsa, and
Simon, and then proceed to explain their importance in the dawn of quantum
computation. Then, we describe the major landmarks: Shor’s factoring,
Grover’s search, and quantum counting.
Chapter 5 is the culmination of all previously explained concepts, as it
includes the description of various quantum algorithms capable of solving
the main problems inside the branch of numerical semigrops. We present
quantum circuit algorithms for the Sylvester denumerant and the numerical
semigroup membership, and adiabatic quantum algorithms for the Ap´ery Set
and the Frobenius problem. We also describe a C++ library called numsem,
specially developed within the context of this doctoral thesis and which
helps us to study the computational hardness of all previously explained
problems from a classical perspective.
This thesis is intended to be autoconclusive at least in the main branches
of mathematics in which it is supported; that is to say numerical
semigroups, computational complexity theory, and quantum computation.
Nevertheless, for the majority of concepts explained here we give references
for the interested reader that wants to delve more into them.
Tue, 01 Jan 2019 00:00:00 GMThttps://hdl.handle.net/11441/872642019-01-01T00:00:00ZA rigid local system with monodromy group 2.J2
https://hdl.handle.net/11441/86652
A rigid local system with monodromy group 2.J2
We exhibit a rigid local system of rank six on the affine line in characteristic p = 5 whose arithmetic and geometric monodromy groups are the finite group 2.J2 (J2 the Hall-Janko
sporadic group) in one of its two (Galois-conjugate) irreducible representation of degree six.
Wed, 01 May 2019 00:00:00 GMThttps://hdl.handle.net/11441/866522019-05-01T00:00:00ZLeaps of the chain of m-integrable derivations in the sense of Hasse-Schmidt
https://hdl.handle.net/11441/86450
Leaps of the chain of m-integrable derivations in the sense of Hasse-Schmidt
Sea k un anillo conmutativo. Los módulos de las k-derivaciones m-integrables (en el sentido de Hasse-Schmidt) de una k-_algebra conmutativa forman una cadena decreciente cuyas inclusiones pueden ser estrictas. Decimos que un entero s > 1 es un leap de una k-algebra conmutativa si las 1-_esima inclusión en la cadena anterior es propia. En esta tesis, estudiamos
el conjunto que forman los saltos en diferentes contextos.
En primer lugar, consideramos k un anillo de característica positiva y probamos que los saltos de cualquier k-algebra conmutativa sólo ocurren en las potencias de la característica.
Luego, nos centramos en estudiar el comportamiento de los módulos de las k-derivaciones m-integrables de una k-algebra conmutativamente generada bajo cambios de base y probamos que si consideramos extensiones de cuerpos trascendentes puras y k-_algebras conmutativamente presentadas, entonces el conjunto de los saltos no cambia bajo el cambio de base. Lo mismo ocurre si consideramos extensiones separables de anillos sobre un cuerpo de característica positiva y k-_algebras conmutativamente generadas.
Por _ultimo calculamos el módulo de las k-derivaciones m-integrables en diferentes curvas planas. Principalmente, damos los generadores de los módulos de las k-derivaciones m- integrables, donde k es un anillo reducido de característica p, del cociente del anillo de polinomios en dos variables con coeficientes en k sobre un ideal generado por la ecuación xn yq donde n o q no es múltiplo de p.; Let k be a commutative ring. The modules of m-integrable k-derivations (in the sense of Hasse-Schmidt) of a commutative k-algebra form a decreasing chain whose inclusions could be strict. We say that an integer s > 1 is a leap of a commutative k-algebra if the s��1-th inclusion of the previous chain is proper. In this thesis, we study the set of leaps in di erent contexts.
First, we consider a commutative ring k of positive characteristic and we prove that leaps of any commutative k-algebra only happen at powers of the characteristic. Thereafter, we focus on studying the behavior of the modules of m-integrable k-derivations of a commutative nitely generated k-algebra under base changes and we prove that if we consider pure transcendental eld extensions and commutative nitely presented k-algebras, then the set of leaps does not change under the base change. The same happens if we consider separable ring extensions over a eld of positive characteristic and commutative nitely generated k-algebras. Finally, we compute the modules of m-integrable k-derivations of di erent plane curves. Mainly, we give the generators of the modules of m-integrable k-derivations, where k is a reduced ring of characteristic p > 0, of the quotient of the polynomial ring in two variables with coe cients in k over the ideal generated by the equation xn �� yq where n or q is not multiple of p.
Thu, 02 May 2019 00:00:00 GMThttps://hdl.handle.net/11441/864502019-05-02T00:00:00ZTorsion homology and cellular approximation
https://hdl.handle.net/11441/85271
Torsion homology and cellular approximation
We describe the role of the Schur multiplier in the structure of the p-torsion of
discrete groups. More concretely, we show how the knowledge of H2G allows us to approximate many groups by colimits of copies of p-groups. Our examples include interesting families of noncommutative infinite groups, including Burnside groups, certain solvable groups and branch groups. We also provide a counterexample for a conjecture of Emmanuel Farjoun.
Wed, 06 Feb 2019 00:00:00 GMThttps://hdl.handle.net/11441/852712019-02-06T00:00:00Z