Permutation classes, sorting algorithms, and lattice paths

A permutation is said to avoid a pattern if it does not contain any subsequence which is order-isomorphic to it. Donald Knuth, in the first volume of his celebrated book "The art of Computer Programming", observed that the permutations that can be computed (or, equivalently, sorted) by some particular data structures can be characterized in terms of pattern avoidance. In more recent years, the topic was reopened several times, while often in terms of sortable permutations rather than computable ones. The idea to sort permutations by using one of Knuth’s devices suggests to look for a deterministic procedure that decides, in linear time, if there exists a sequence of operations which is able to convert a given permutation into the identical one. In this thesis we show that, for the stack and the restricted deques, there exists an unique way to implement such a procedure. Moreover, we use these sorting procedures to create new sorting algorithms, and we prove some unexpected commutation properties between these procedures and the base step of bubblesort. We also show that the permutations that can be sorted by a combination of the base steps of bubblesort and its dual can be expressed, once again, in terms of pattern avoidance. In the final chapter we give an alternative proof of some enumerative results, in particular for the classes of permutations that can be sorted by the two restricted deques. It is well-known that the permutations that can be sorted through a restricted deque are counted by the Schrӧder numbers. In the thesis, we show how the deterministic sorting procedures yield a bijection between sortable permutations and Schrӧder paths.

Interacting bosons and fermions in three-dimensional optical lattice potentials

This thesis reports on the realization, characterization and analysis of ultracold bosonic and fermionic atoms in three-dimensional optical lattice potentials. Ultracold quantum gases in optical lattices can be regarded as ideal model systems to investigate quantum many-body physics. In this work interacting ensembles of bosonic 87Rb and fermionic 40K atoms are employed to study equilibrium phases and nonequilibrium dynamics. The investigations are enabled by a versatile experimental setup, whose core feature is a blue-detuned optical lattice that is combined with Feshbach resonances and a red-detuned dipole trap to allow for independent control of tunneling, interactions and external confinement. The Fermi-Hubbard model, which plays a central role in the theoretical description of strongly correlated electrons, is experimentally realized by loading interacting fermionic spin mixtures into the optical lattice. Using phase-contrast imaging the in-situ size of the atomic density distribution is measured, which allows to extract the global compressibility of the many-body state as a function of interaction and external confinement. Thereby, metallic and insulating phases are clearly identified. At strongly repulsive interaction, a vanishing compressibility and suppression of doubly occupied lattice sites signal the emergence of a fermionic Mott insulator. In a second series of experiments interaction effects in bosonic lattice quantum gases are analyzed. Typically, interactions between microscopic particles are described as two-body interactions. As such they are also contained in the single-band Bose-Hubbard model. However, our measurements demonstrate the presence of multi-body interactions that effectively emerge via virtual transitions of atoms to higher lattice bands. These findings are enabled by the development of a novel atom optical measurement technique: In quantum phase revival spectroscopy periodic collapse and revival dynamics of the bosonic matter wave field are induced. The frequencies of the dynamics are directly related to the on-site interaction energies of atomic Fock states and can be read out with high precision. The third part of this work deals with mixtures of bosons and fermions in optical lattices, in which the interspecies interactions are accurately controlled by means of a Feshbach resonance. Studies of the equilibrium phases show that the bosonic superfluid to Mott insulator transition is shifted towards lower lattice depths when bosons and fermions interact attractively. This observation is further analyzed by applying quantum phase revival spectroscopy to few-body systems consisting of a single fermion and a coherent bosonic field on individual lattice sites. In addition to the direct measurement of Bose-Fermi interaction energies, Bose-Bose interactions are proven to be modified by the presence of a fermion. This renormalization of bosonic interaction energies can explain the shift of the Mott insulator transition. The experiments of this thesis lay important foundations for future studies of quantum magnetism with fermionic spin mixtures as well as for the realization of complex quantum phases with Bose-Fermi mixtures. They furthermore point towards physics that reaches beyond the single-band Hubbard model.

Baryons in the chiral regime

Quantum Chromodynamics (QCD) is the theory of strong interactions, one of the four fundamental forces in our Universe. It describes the interaction of gluons and quarks which build up hadrons like protons and neutrons. Most of the visible matter in our universe is made of protons and neutrons. Hence, we are interested in their fundamental properties like their masses, their distribution of charge and their shape. \\rnThe only known theoretical, non-perturbative and {\it ab initio} method to investigate hadron properties at low energies is lattice Quantum Chromodynamics (lattice QCD). However, up-to-date simulations (especially for baryonic quantities) do not achieve the accuracy of experiments. In fact, current simulations do not even reproduce the experimental values for the form factors. The question arises wether these deviations can be explained by systematic effects in lattice QCD simulations.rnrnThis thesis is about the computation of nucleon form factors and other hadronic quantities from lattice QCD. So called Wilson fermions are used and the u- and d-quarks are treated fully dynamically. The simulations were performed using gauge ensembles with a range of lattice spacings, volumes and pion masses.\\rnFirst of all, the lattice spacing was set to be able to make contact between the lattice results and their experimental complement and to be able to perform a continuum extrapolation. The light quark mass has been computed and found to be $m_{ud}^{\overline{\text{MS}}}(2\text{ GeV}) = 3.03(17)(38)\text{ MeV}$. This value is in good agreement with values from experiments and other lattice determinations.\\rnElectro-magnetic and axial form factors of the nucleon have been calculated. From these form factors the nucleon radii and the coupling constants were computed. The different ensembles enabled us to investigate systematically the dependence of these quantities on the volume, the lattice spacing and the pion mass.\newpage Finally we perform a continuum extrapolation and chiral extrapolations to the physical point.\\rnIn addition, we investigated so called excited state contributions to these observables. A technique was used, the summation method, which reduces these effects significantly and a much better agreement with experimental data was achieved. On the lattice, the Dirac radius and the axial charge are usually found to be much smaller than the experimental values. However, due to the carefully investigation of all the afore-mentioned systematic effects we get $\langle r_1^2\rangle_{u-d}=0.627(54)\text{ fm}^2$ and $g_A=1.218(92)$, which is in agreement with the experimental values within the errors.rnrnThe first three chapters introduce the theoretical background of form factors of the nucleon and lattice QCD in general. In chapter four the lattice spacing is determined. The computation of nucleon form factors is described in chapter five where systematic effects are investigated. All results are presented in chapter six. The thesis ends with a summary of the results and identifies options to complement and extend the calculations presented. rn

Su(3) lattice gauge theories and spin chains

I modelli su reticolo con simmetrie SU(n) sono attualmente oggetto di studio sia dal punto di vista sperimentale, sia dal punto di vista teorico; particolare impulso alla ricerca in questo campo è stato dato dai recenti sviluppi in campo sperimentale per quanto riguarda la tecnica dell’intrappolamento di atomi ultrafreddi in un reticolo ottico. In questa tesi viene studiata, sia con tecniche analitiche sia con simulazioni numeriche, la generalizzazione del modello di Heisenberg su reticolo monodimensionale a simmetria SU(3). In particolare, viene proposto un mapping tra il modello di Heisenberg SU(3) e l’Hamiltoniana con simmetria SU(2) bilineare-biquadratica con spin 1. Vengono inoltre presentati nuovi risultati numerici ottenuti con l’algoritmo DMRG che confermano le previsioni teoriche in letteratura sul modello in esame. Infine è proposto un approccio per la formulazione della funzione di partizione dell’Hamiltoniana bilineare-biquadratica a spin-1 servendosi degli stati coerenti per SU(3).

Hadronic matrix elements in lattice QCD

The lattice formulation of Quantum ChromoDynamics (QCD) has become a reliable tool providing an ab initio calculation of low-energy quantities. Despite numerous successes, systematic uncertainties, such as discretisation effects, finite-size effects, and contaminations from excited states, are inherent in any lattice calculation. Simulations with controlled systematic uncertainties and close to the physical pion mass have become state-of-the-art. We present such a calculation for various hadronic matrix elements using non-perturbatively O(a)-improved Wilson fermions with two dynamical light quark flavours. The main topics covered in this thesis are the axial charge of the nucleon, the electro-magnetic form factors of the nucleon, and the leading hadronic contributions to the anomalous magnetic moment of the muon. Lattice simulations typically tend to underestimate the axial charge of the nucleon by 5 − 10%. We show that including excited state contaminations using the summed operator insertion method leads to agreement with the experimentally determined value. Further studies of systematic uncertainties reveal only small discretisation effects. For the electro-magnetic form factors of the nucleon, we see a similar contamination from excited states as for the axial charge. The electro-magnetic radii, extracted from a dipole fit to the momentum dependence of the form factors, show no indication of finite-size or cutoff effects. If we include excited states using the summed operator insertion method, we achieve better agreement with the radii from phenomenology. The anomalous magnetic moment of the muon can be measured and predicted to very high precision. The theoretical prediction of the anomalous magnetic moment receives contribution from strong, weak, and electro-magnetic interactions, where the hadronic contributions dominate the uncertainties. A persistent 3σ tension between the experimental determination and the theoretical calculation is found, which is considered to be an indication for physics beyond the Standard Model. We present a calculation of the connected part of the hadronic vacuum polarisation using lattice QCD. Partially twisted boundary conditions lead to a significant improvement of the vacuum polarisation in the region of small momentum transfer, which is crucial in the extraction of the hadronic vacuum polarisation.

Imaging and modeling of pore scale processes in porous media using X-ray computed tomography and lattice Boltzmann solver

In der Erdöl– und Gasindustrie sind bildgebende Verfahren und Simulationen auf der Porenskala im Begriff Routineanwendungen zu werden. Ihr weiteres Potential lässt sich im Umweltbereich anwenden, wie z.B. für den Transport und Verbleib von Schadstoffen im Untergrund, die Speicherung von Kohlendioxid und dem natürlichen Abbau von Schadstoffen in Böden. Mit der Röntgen-Computertomografie (XCT) steht ein zerstörungsfreies 3D bildgebendes Verfahren zur Verfügung, das auch häufig für die Untersuchung der internen Struktur geologischer Proben herangezogen wird. Das erste Ziel dieser Dissertation war die Implementierung einer Bildverarbeitungstechnik, die die Strahlenaufhärtung der Röntgen-Computertomografie beseitigt und den Segmentierungsprozess dessen Daten vereinfacht. Das zweite Ziel dieser Arbeit untersuchte die kombinierten Effekte von Porenraumcharakteristika, Porentortuosität, sowie die Strömungssimulation und Transportmodellierung in Porenräumen mit der Gitter-Boltzmann-Methode. In einer zylindrischen geologischen Probe war die Position jeder Phase auf Grundlage der Beobachtung durch das Vorhandensein der Strahlenaufhärtung in den rekonstruierten Bildern, das eine radiale Funktion vom Probenrand zum Zentrum darstellt, extrahierbar und die unterschiedlichen Phasen ließen sich automatisch segmentieren. Weiterhin wurden Strahlungsaufhärtungeffekte von beliebig geformten Objekten durch einen Oberflächenanpassungsalgorithmus korrigiert. Die Methode der „least square support vector machine” (LSSVM) ist durch einen modularen Aufbau charakterisiert und ist sehr gut für die Erkennung und Klassifizierung von Mustern geeignet. Aus diesem Grund wurde die Methode der LSSVM als pixelbasierte Klassifikationsmethode implementiert. Dieser Algorithmus ist in der Lage komplexe geologische Proben korrekt zu klassifizieren, benötigt für den Fall aber längere Rechenzeiten, so dass mehrdimensionale Trainingsdatensätze verwendet werden müssen. Die Dynamik von den unmischbaren Phasen Luft und Wasser wird durch eine Kombination von Porenmorphologie und Gitter Boltzmann Methode für Drainage und Imbibition Prozessen in 3D Datensätzen von Böden, die durch synchrotron-basierte XCT gewonnen wurden, untersucht. Obwohl die Porenmorphologie eine einfache Methode ist Kugeln in den verfügbaren Porenraum einzupassen, kann sie dennoch die komplexe kapillare Hysterese als eine Funktion der Wassersättigung erklären. Eine Hysterese ist für den Kapillardruck und die hydraulische Leitfähigkeit beobachtet worden, welche durch die hauptsächlich verbundenen Porennetzwerke und der verfügbaren Porenraumgrößenverteilung verursacht sind. Die hydraulische Konduktivität ist eine Funktion des Wassersättigungslevels und wird mit einer makroskopischen Berechnung empirischer Modelle verglichen. Die Daten stimmen vor allem für hohe Wassersättigungen gut überein. Um die Gegenwart von Krankheitserregern im Grundwasser und Abwässern vorhersagen zu können, wurde in einem Bodenaggregat der Einfluss von Korngröße, Porengeometrie und Fluidflussgeschwindigkeit z.B. mit dem Mikroorganismus Escherichia coli studiert. Die asymmetrischen und langschweifigen Durchbruchskurven, besonders bei höheren Wassersättigungen, wurden durch dispersiven Transport aufgrund des verbundenen Porennetzwerks und durch die Heterogenität des Strömungsfeldes verursacht. Es wurde beobachtet, dass die biokolloidale Verweilzeit eine Funktion des Druckgradienten als auch der Kolloidgröße ist. Unsere Modellierungsergebnisse stimmen sehr gut mit den bereits veröffentlichten Daten überein.

Plasmonic nanoparticles as sensors : a novel approach to quantify adsorption and diffusion kinetics

Biosensors find wide application in clinical diagnostics, bioprocess control and environmental monitoring. They should not only show high specificity and reproducibility but also a high sensitivity and stability of the signal. Therefore, I introduce a novel sensor technology based on plasmonic nanoparticles which overcomes both of these limitations. Plasmonic nanoparticles exhibit strong absorption and scattering in the visible and near-infrared spectral range. The plasmon resonance, the collective coherent oscillation mode of the conduction band electrons against the positively charged ionic lattice, is sensitive to the local environment of the particle. I monitor these changes in the resonance wavelength by a new dark-field spectroscopy technique. Due to a strong light source and a highly sensitive detector a temporal resolution in the microsecond regime is possible in combination with a high spectral stability. This opens a window to investigate dynamics on the molecular level and to gain knowledge about fundamental biological processes.rnFirst, I investigate adsorption at the non-equilibrium as well as at the equilibrium state. I show the temporal evolution of single adsorption events of fibrinogen on the surface of the sensor on a millisecond timescale. Fibrinogen is a blood plasma protein with a unique shape that plays a central role in blood coagulation and is always involved in cell-biomaterial interactions. Further, I monitor equilibrium coverage fluctuations of sodium dodecyl sulfate and demonstrate a new approach to quantify the characteristic rate constants which is independent of mass transfer interference and long term drifts of the measured signal. This method has been investigated theoretically by Monte-Carlo simulations but so far there has been no sensor technology with a sufficient signal-to-noise ratio.rnSecond, I apply plasmonic nanoparticles as sensors for the determination of diffusion coefficients. Thereby, the sensing volume of a single, immobilized nanorod is used as detection volume. When a diffusing particle enters the detection volume a shift in the resonance wavelength is introduced. As no labeling of the analyte is necessary the hydrodynamic radius and thus the diffusion properties are not altered and can be studied in their natural form. In comparison to the conventional Fluorescence Correlation Spectroscopy technique a volume reduction by a factor of 5000-10000 is reached.

Hadronic correlation functions with quark-disconnected contributions in lattice QCD

One of the fundamental interactions in the Standard Model of particle physicsrnis the strong force, which can be formulated as a non-abelian gauge theoryrncalled Quantum Chromodynamics (QCD). rnIn the low-energy regime, where the QCD coupling becomes strong and quarksrnand gluons are confined to hadrons, a perturbativernexpansion in the coupling constant is not possible.rnHowever, the introduction of a four-dimensional Euclidean space-timernlattice allows for an textit{ab initio} treatment of QCD and provides arnpowerful tool to study the low-energy dynamics of hadrons.rnSome hadronic matrix elements of interest receive contributionsrnfrom diagrams including quark-disconnected loops, i.e. disconnected quarkrnlines from one lattice point back to the same point. The calculation of suchrnquark loops is computationally very demanding, because it requires knowledge ofrnthe all-to-all propagator. In this thesis we use stochastic sources and arnhopping parameter expansion to estimate such propagators.rnWe apply this technique to study two problems which relay crucially on therncalculation of quark-disconnected diagrams, namely the scalar form factor ofrnthe pion and the hadronic vacuum polarization contribution to the anomalousrnmagnet moment of the muon.rnThe scalar form factor of the pion describes the coupling of a charged pion torna scalar particle. We calculate the connected and the disconnected contributionrnto the scalar form factor for three different momentum transfers. The scalarrnradius of the pion is extracted from the momentum dependence of the form factor.rnThe use ofrnseveral different pion masses and lattice spacings allows for an extrapolationrnto the physical point. The chiral extrapolation is done using chiralrnperturbation theory ($chi$PT). We find that our pion mass dependence of thernscalar radius is consistent with $chi$PT at next-to-leading order.rnAdditionally, we are able to extract the low energy constant $ell_4$ from thernextrapolation, and ourrnresult is in agreement with results from other lattice determinations.rnFurthermore, our result for the scalar pion radius at the physical point isrnconsistent with a value that was extracted from $pipi$-scattering data. rnThe hadronic vacuum polarization (HVP) is the leading-order hadronicrncontribution to the anomalous magnetic moment $a_mu$ of the muon. The HVP canrnbe estimated from the correlation of two vector currents in the time-momentumrnrepresentation. We explicitly calculate the corresponding disconnectedrncontribution to the vector correlator. We find that the disconnectedrncontribution is consistent with zero within its statistical errors. This resultrncan be converted into an upper limit for the maximum contribution of therndisconnected diagram to $a_mu$ by using the expected time-dependence of therncorrelator and comparing it to the corresponding connected contribution. Wernfind the disconnected contribution to be smaller than $approx5%$ of thernconnected one. This value can be used as an estimate for a systematic errorrnthat arises from neglecting the disconnected contribution.rn

Edge states and zero modes in quadratic fermionic models on a 1-D lattice

In una formulazione rigorosa della teoria quantistica, la definizione della varietà Riemanniana spaziale su cui il sistema è vincolato gioca un ruolo fondamentale. La presenza di un bordo sottolinea l'aspetto quantistico del sistema: l'imposizione di condizioni al contorno determina la discretizzazione degli autovalori del Laplaciano, come accade con condizioni note quali quelle periodiche, di Neumann o di Dirichlet. Tuttavia, non sono le uniche possibili. Qualsiasi condizione al bordo che garantisca l'autoaggiunzione dell' operatore Hamiltoniano è ammissibile. Tutte le possibili boundary conditions possono essere catalogate a partire dalla richiesta di conservazione del flusso al bordo della varietà. Alcune possibili condizioni al contorno, permettono l'esistenza di stati legati al bordo, cioè autostati dell' Hamiltoniana con autovalori negativi, detti edge states. Lo scopo di questa tesi è quello di investigare gli effetti di bordo in sistemi unidimensionali implementati su un reticolo discreto, nella prospettiva di capire come simulare proprietà di edge in un reticolo ottico. Il primo caso considerato è un sistema di elettroni liberi. La presenza di edge states è completamente determinata dai parametri di bordo del Laplaciano discreto. Al massimo due edge states emergono, e possono essere legati all' estremità destra o sinistra della catena a seconda delle condizioni al contorno. Anche il modo in cui decadono dal bordo al bulk e completamente determinato dalla scelta delle condizioni. Ammettendo un' interazione quadratica tra siti primi vicini, un secondo tipo di stati emerge in relazione sia alle condizioni al contorno che ai parametri del bulk. Questi stati sono chiamati zero modes, in quanto esiste la possibilità che siano degeneri con lo stato fondamentale. Per implementare le più generali condizioni al contorno, specialmente nel caso interagente, è necessario utilizzare un metodo generale per la diagonalizzazione, che estende la tecnica di Lieb-Shultz-Mattis per Hamiltoniane quadratiche a matrici complesse.

Quantum simulation of (1+1)D QED via a Zn lattice Gauge theory

La simulazione di un sistema quantistico complesso rappresenta ancora oggi una sfida estremamente impegnativa a causa degli elevati costi computazionali. La dimensione dello spazio di Hilbert cresce solitamente in modo esponenziale all'aumentare della taglia, rendendo di fatto impossibile una implementazione esatta anche sui più potenti calcolatori. Nel tentativo di superare queste difficoltà, sono stati sviluppati metodi stocastici classici, i quali tuttavia non garantiscono precisione per sistemi fermionici fortemente interagenti o teorie di campo in regimi di densità finita. Di qui, la necessità di un nuovo metodo di simulazione, ovvero la simulazione quantistica. L'idea di base è molto semplice: utilizzare un sistema completamente controllabile, chiamato simulatore quantistico, per analizzarne un altro meno accessibile. Seguendo tale idea, in questo lavoro di tesi si è utilizzata una teoria di gauge discreta con simmetria Zn per una simulazione dell'elettrodinamica quantistica in (1+1)D, studiando alcuni fenomeni di attivo interesse di ricerca, come il diagramma di fase o la dinamica di string-breaking, che generalmente non sono accessibili mediante simulazioni classiche. Si propone un diagramma di fase del modello caratterizzato dalla presenza di una fase confinata, in cui emergono eccitazioni mesoniche ed antimesoniche, cioè stati legati particella-antiparticella, ed una fase deconfinata.

Kaon and D meson masses with N_f = 2+1+1 twisted mass lattice QCD

We discuss the computation of the kaon and D meson masses in the N_f = 2+1+1 twisted mass lattice QCD setup, where explicit heavy flavor and parity breaking occurs at finite lattice spacing. We present three methods suitable in this context and verify their consistency.