Manual de preparació per a olimpíades i competicions matemàtiques

Treball de recerca realitzat per un alumne d’ensenyament secundari i guardonat amb un Premi CIRIT per fomentar l'esperit científic del Jovent l’any 2008. Es presenta als interessats en les competicions de matemàtiques un manual sòlid, compacte, però sintetitzat, que els permeti, complementar i ampliar els seus coneixements matemàtics dirigits a aquestes competicions. En la primera part, es tracten les olimpíades matemàtiques més importants estatals i arreu del món per tal de donar-les a conèixer al lector. A continuació s'expliquen les tècniques generals més utilitzades per construir una demostració determinada. Finalment, es tanca la secció parlant de la creació de problemes, un apartat que permet estimular i potenciar la pròpia creativitat. En la segona part, es troba el propi cos del manual, amb una gran quantitat de problemas solucionats. Per tal de facilitar-ne l'ús, s'ha dividit en quatre grans temes, corresponents als que es treballen a les Olimpíades Matemàtiques: teoria de nombres o aritmètica, geometria, àlgebra i combinatòria. Cada un d'aquests temes es troba, a la vegada, dividit en dues seccions: la de teoremes i conceptes, en què s'enuncien els principals teoremes i fórmules que el lector necessita conéixer, i la d'exercicis i problemes on s’han recollit multitud de problemes provinents de diferents competicions, indicant el grau de dificultat - cal remarcar però, que el present document és una reducció del treball original, per això s'ha decidit només incloure-hi l'apartat d'aritmètica i ometre els altres tres -.

Pitàgores: música i matemàtiques

Treball de recerca realitzat per un alumne d'ensenyament secundari i guardonat amb un Premi CIRIT per fomentar l'esperit cientí­fic del Jovent l'any 2009. L'objectiu general del treball de recerca és estudiar la figura de Pitàgores, així com analitzar la seva filosofia i endinsar-se en les relacions que va establir entre la música i les matemàtiques. El treball consta de dues parts diferenciades, una teòrica i una pràctica. En la part teòrica s'estudien l'Escola Pitagòrica i les seves aportacions al camp musical. Es descriuen les experimentacions de Pitàgores amb el monocordi i es dóna explicació matemàtica a les escales musicals sorgides des de llavors, així com també es comenta la teoria de la música de les esferes. En la part pràctica, l'alumne empra tot el seu bagatge matemàtic i musical, adquirit al llarg de l'elaboració del cos teòric del treball per arribar a la construcció de dos tipus de monocordi.

Contractive probability metrics and asymptotic behavior of dissipative kinetic equations

The present notes are intended to present a detailed review of the existing results in dissipative kinetic theory which make use of the contraction properties of two main families of probability metrics: optimal mass transport and Fourier-based metrics. The first part of the notes is devoted to a self-consistent summary and presentation of the properties of both probability metrics, including new aspects on the relationships between them and other metrics of wide use in probability theory. These results are of independent interest with potential use in other contexts in Partial Differential Equations and Probability Theory. The second part of the notes makes a different presentation of the asymptotic behavior of Inelastic Maxwell Models than the one presented in the literature and it shows a new example of application: particle's bath heating. We show how starting from the contraction properties in probability metrics, one can deduce the existence, uniqueness and asymptotic stability in classical spaces. A global strategy with this aim is set up and applied in two dissipative models.

Data size sufficiency analyses of haplotype inference algortihms

We present experimental and theoretical analyses of data requirements for haplotype inference algorithms. Our experiments include a broad range of problem sizes under two standard models of tree distribution and were designed to yield statistically robust results despite the size of the sample space. Our results validate Gusfield's conjecture that a population size of n log n is required to give (with high probability) sufficient information to deduce the n haplotypes and their complete evolutionary history. The experimental results inspired our experimental finding with theoretical bounds on the population size. We also analyze the population size required to deduce some fixed fraction of the evolutionary history of a set of n haplotypes and establish linear bounds on the required sample size. These linear bounds are also shown theoretically.

Contribució de Pietro Mengoli al concepte de límit a través d'una teoria de les quasi proporcions

El treball de recerca que aquí es presenta és l’estudi dels tres primers "elementa" de la "Geometriae Speciosae Elementa" (Bolonya, 1659) de Pietro Mengoli (1625-1686), que fou possiblement el deixeble més original de Bonaventura Cavalieri (1598-1647). En aquesta obra Mengoli desenvolupa un nou mètode per calcular quadratures utilitzant una teoria numèrica anomenada de “quasi proporcions”. Mengoli fonamenta les quasi proporcions en la teoria de proporcions del llibre cinquè dels "Elements" d’Euclides, a la qual hi afegeix unes nocions originals: raó “quasi nul•la”, “quasi infinita” i “quasi un nombre”. Una exhaustiva anàlisi d’aquesta teoria demostra l’originalitat de l’obra de Mengoli tant pel que fa a la seva forma d’exposició com pel que fa al seu contingut.

Una aproximació al pensament algebraic a l'Espanya del segle XVI: estudi del manuscrit 2294 de la Biblioteca de la Universitat de Salamanca

Aquest treball analitza el “Tratado y libro de arte mayor o álgebra” que forma part del manuscrit 2294 de la Biblioteca de la Universitat de Salamanca, datat el 1590. El seu autor és Diego Pérez de Mesa. L’objectiu d’aquest estudi és aportar nous elements que ajudin a entendre quin era l’estatus de l’àlgebra a la Península Ibèrica en un segle que va ser clau en el seu desenvolupament. Primer es descriu el manuscrit i després es reflexiona sobre les seves aportacions a la matemàtica, mostrant algunes característiques originals d’aquesta àlgebra enfront d’altres àlgebres de la Península Ibèrica del segle XVI.

A class of stochastic games with infinitely many interacting agents related to Glauber dynamics on random graphs

We introduce and study a class of infinite-horizon nonzero-sum non-cooperative stochastic games with infinitely many interacting agents using ideas of statistical mechanics. First we show, in the general case of asymmetric interactions, the existence of a strategy that allows any player to eliminate losses after a finite random time. In the special case of symmetric interactions, we also prove that, as time goes to infinity, the game converges to a Nash equilibrium. Moreover, assuming that all agents adopt the same strategy, using arguments related to those leading to perfect simulation algorithms, spatial mixing and ergodicity are proved. In turn, ergodicity allows us to prove “fixation”, i.e. that players will adopt a constant strategy after a finite time. The resulting dynamics is related to zerotemperature Glauber dynamics on random graphs of possibly infinite volume.

On locally finite transitive two-ended digraphs

Projecte de recerca elaborat a partir d’una estada al Department de Matemàtica Aplicada de la Montanuniversität Leoben, Àustria, entre agost i desembre del 2006. L’ objectiu ha estat fer recerca sobre digrafs infinits amb dos finals, connexos i localment finits, i, en particular, en digrafs amb dos finals i altament arc-transitius. Malnic, Marusic et al. van introduir un nou tipus de relació d’equivalència en els vèrtexs d’un dígraf, anomenades relacions d’assolibilitat, que generalitzen i tenen el seu origen en un problema posat per Cameron et al., on les classes de la relació d’equivalència eren vèrtexs que pertanyien a un camí alternat del dígraf . Malnic et al. en el mencionat article van establir connexions ben estretes entre aquestes relacions d’assolibilitat i l'estructura de finals i creixement dels digrafs localment finits i transitius. En aquest treball, s’ha caracteritzat per complet aquestes relacions d’assolibitat en el cas de dígrafs localment finits i transitius amb exactament dos finals, en termes de la descomposició en números primers del número de línies que genera el digraf amb dos finals. A més, es nega la Conjectura 1 sostinguda per Seifter que afirmava que un digraf connex localment finit amb més d’un final era necessàriament o be 0-, 1- o altament arc-transitiu. Seifer havia donat una solució parcial a la conjectura pel cas de digrafs regulars amb grau primer que tinguin un conjunt de tall connex. En aquest treball, es descriu una família infinita de dígrafs regulars de grau dos, amb dos finals, exactament 2-arc transitius i no 3-arc transitius. Així, es nega la Conjectura de Seifter en el cas general, fins i tot per grau primer. Tot i així, la solució parcial donada per Seifter en el seu article és en cert sentit la millor possible i l'existència un conjunt de tall connex essencial.

Coupling and monotonicity of queueing processes

The main purpose of this work is to give a survey of main monotonicity properties of queueing processes based on the coupling method. The literature on this topic is quite extensive, and we do not consider all aspects of this topic. Our more concrete goal is to select the most interesting basic monotonicity results and give simple and elegant proofs. Also we give a few new (or revised) proofs of a few important monotonicity properties for the queue-size and workload processes both in single-server and multi- server systems. The paper is organized as follows. In Section 1, the basic notions and results on coupling method are given. Section 2 contains known coupling results for renewal processes with focus on construction of synchronized renewal instants for a superposition of independent renewal processes. In Section 3, we present basic monotonicity results for the queue-size and workload processes. We consider both discrete-and continuous-time queueing systems with single and multi servers. Less known results on monotonicity of queueing processes with dependent service times and interarrival times are also presented. Section 4 is devoted to monotonicity of general Jackson-type queueing networks with Markovian routing. This section is based on the notable paper [17]. Finally, Section 5 contains elements of stability analysis of regenerative queues and networks, where coupling and monotonicity results play a crucial role to establish minimal suficient stability conditions. Besides, we present some new monotonicity results for tandem networks.

A public-key cryptosystem based on second order linear sequences

Based on Lucas functions, an improved version of the Diffie-Hellman distribution key scheme and to the ElGamal public key cryptosystem scheme are proposed, together with an implementation and computational cost. The security relies on the difficulty of factoring an RSA integer and on the difficulty of computing the discrete logarithm.

Les joies de la trigonometria

Treball de recerca realitzat per un alumne d’ensenyament secundari i guardonat amb un Premi CIRIT per fomentar l'esperit científic del Jovent l’any 2008. S’ha desenvolupat una aplicació informàtica per fer la trigonometria més entenedora a estudiants a partir del segon cicle d’ESO fins a universitaris. Aquest document és una descripció d’aquest programa i no la mateixa aplicació.

Aplicacions contínues entre espais classificadors de grups p-locals finits

Projecte de recerca elaborat a partir d’una estada a la Universitat d'Aberdeen, Irlanda, entre abril i maig del 2007. Un dels objectius de la topologia algebraica és la de classificar espais topològics i aplicacions continues mitjançant estructures algebraiques associades a ells. És a dir, mitjançant diferents maneres d'associar un objecte algebraic a un espai, es pretén reflectir el màxim de la seva estructura topològica. D'altra banda, donat un grup G, se li pot associar un espai topològic BG anomenat l'espai classificador del grup que és l'espai que classifica els G-fibrats vectorials. El programa d'estudiar el tipus d'homotopia d'espais i aplicacions contínues ha donat molts fruits quan els espais que s'estudien són espais classificadors (en particular, grups finits i grups de Lie). En particular, a causa del fet que moltes propietats algebraiques del grup queden reflectides en l'espai classificador, aquest tipus d'espais juguen un paper molt important en la interelació entre l'àlgebra i la topologia. Per exemple, els treballs de Dwyer, Zabrodsky i Mislin identifiquen les aplicacions contínues entre espais classificadors d'un p-grup i un grup qualsevol amb els morfismes entre grups llevat conjugació. L’objectiu d’aquest projecte és el de descriure les aplicacions contínues entre p-completats d’espais classificadors a partir d’informació algebraica referent a l’estructura de p-subgrups de cadascun d’ells.

Spot inversion in the Heston model

We analyse the Heston stochastic volatility model under an inversion of spot. The result is that under the appropriate measure changes the resulting process is again a Heston type process whose parameters can be explicitly determined from those of the original process. This behaviour can be interpreted as some measure of sanity of the Heston model but does not seem to be a general feature of stochastic volatility processes.

Jugant amb l'atzar i la probabilitat

Treball de recerca realitzat per un alumne d'ensenyament secundari i guardonat amb un Premi CIRIT per fomentar l'esperit cientí­fic del Jovent l'any 2009. Quins científics van interessar-se per la probabilitat en els seus inicis?, quins altres van fer-la evolucionar? i quins conceptes coneixem i apliquem a l'actualitat? són preguntes que el treball teòric es proposa respondre. Pel que fa a la part pràctica del treball, el seu objectiu és el de crear un mecanisme capaç de generar nombres aleatoris a partir d'un taulell condicionat per paràmetres. El treball s'estructura en 4 blocs que aborden diversos camps de la probabilitat: la història de la probabilitat, els conceptes bàsics de la probabilitat, una introducció pràctica al mecanisme aleatori i el treball de camp. Els resultats finals rebel·len la possibilitat de generar nombres aleatoris a partir d'aparells senzills.

Stabilized Petrov-Galerkin methods for the convection-diffusion-reaction and the Helmholtz equations

We present two new stabilized high-resolution numerical methods for the convection–diffusion–reaction (CDR) and the Helmholtz equations respectively. The work embarks upon a priori analysis of some consistency recovery procedures for some stabilization methods belonging to the Petrov–Galerkin framework. It was found that the use of some standard practices (e.g. M-Matrices theory) for the design of essentially non-oscillatory numerical methods is not feasible when consistency recovery methods are employed. Hence, with respect to convective stabilization, such recovery methods are not preferred. Next, we present the design of a high-resolution Petrov–Galerkin (HRPG) method for the 1D CDR problem. The problem is studied from a fresh point of view, including practical implications on the formulation of the maximum principle, M-Matrices theory, monotonicity and total variation diminishing (TVD) finite volume schemes. The current method is next in line to earlier methods that may be viewed as an upwinding plus a discontinuity-capturing operator. Finally, some remarks are made on the extension of the HRPG method to multidimensions. Next, we present a new numerical scheme for the Helmholtz equation resulting in quasi-exact solutions. The focus is on the approximation of the solution to the Helmholtz equation in the interior of the domain using compact stencils. Piecewise linear/bilinear polynomial interpolation are considered on a structured mesh/grid. The only a priori requirement is to provide a mesh/grid resolution of at least eight elements per wavelength. No stabilization parameters are involved in the definition of the scheme. The scheme consists of taking the average of the equation stencils obtained by the standard Galerkin finite element method and the classical finite difference method. Dispersion analysis in 1D and 2D illustrate the quasi-exact properties of this scheme. Finally, some remarks are made on the extension of the scheme to unstructured meshes by designing a method within the Petrov–Galerkin framework.