Nous établissons une nouvelle majoration optimale pour les plus petites valeurs propres de l'opérateur de Dirac sur une hypersurface compacte de l'espace hyperbolique. / We prove a new upper bound for the smallest eigenvalues of the Dirac operator on a compact hypersurface of the hyperbolic space.

<p> A string is a sequence of various simple elements. The most straightforward examples of strings are English words-concatenations of the 26 letters of the English alphabet. A repetition in a string x is a nonempty substring of the form x[i..j] = u^k, k ≥ 2. The study of repetitions in strings is as old as the study of strings themselves. Furthermore, the identification of repetitions in a given finite string still remains an important topic in a variety of contexts: pattern-matching, computational biology, data compression, cryptology, and many other areas. </p> <p> A run in a string xis a substring in the form x[i..j] = u^kv, k ≥ 2 where v is a prefix of u, u is not a repetition itself, and this substring x[i..j] is neither left-extendible nor right-extendible. The notion of runs thus captures the notion of leftmost maximal repetitions and allows for a succinct notation [M89]. The maximal number of runs over all strings of length n is denoted as p(n). To determine the properties of the function p(n) is an important aspect of the research in periodicities in strings. </p> <p> Prior to the asymptotic lower bound presented by Franek and myself in [FY06] (presented here in Chapter 2), there had been no known non-trivial lower bound for p(n), asymptotic or otherwise. A result suggesting a possible lower bound was presented by Franek, Simpson and Smyth in 2003, introducing a construction of a sequence of strings {xn}~=0, so that limn→∞ r(Xn)/[Xn] = 3/(1+√5) ≈ 0.927 [FSS03]. Theirmethod was extended to provide a true asymptotic lower bound in [FY06]. In the first part of Chapter 2, the recursive construction of the sequence of strings from [FSS03] is presented with all details not discussed in either [FSS03] or [FY06]. In the second part of Chapter 2, a construction of the lower bound is presented with all details. This part represents my original contribution to the research. </p> <p> I designed a new approach to generate strings that are "rich in runs" other then the one used in [FSS03] and [FY06]. A similar approach as in Chapter 2 is used to construct a lower bound for p(n) using the alternate construction of sequences of strings. This new construction method gives, interestingly, sequences with the same limit as in [FY06], thus giving some support to the conjecture that limn→∞ p(n)/n = 3/(1+√5) stated in [FSS03]. This method is presented in Chapter 3. The whole Chapter 3 thus represents another part of my original contribution to the research. </p> <p> It had been known since the 1980's that the number of repetitions in a string of length n is at most of the order O(n log n). A remarkable result by Kolpakov and Kucherov in 2000 showed that p(n) was in fact bounded by a function linear in n [KK00]. Their approach only. provided the existence of such a function, not the concrete values of its constants. Recently, Rytter improved the upper bound of p(n) to 5n. [R06). The paper by Rytter was published in a conference proceedings and as such lacked many details in some areas and was bit too vague. In Chapter 4 I present Rytter's proof with all relevant details filled in. Through a private communication I learned at the time of writing of this thesis that the upper bound had been improved by Rytter, and independently by Smyth, Simpson, and Puglisi to 3.5n. The latest upper bound is supposed to be now as low as 1.5n. However, none of the upper bounds better than 5n has been published yet. </p> <p> In the last chapter I discuss my conclusions and point out the directions for the future research. </p> / Thesis / Master of Science (MSc)

Nós estudamos a dinâmica do operador de renormalização atuando no espaço de pares (?, t), onde ? é um difeomorfismo e t ? [0, 1], interpretados como aplicações unimodais ? o qt, onde qt(x) = -2t|x|? + 2t - 1. Estabelecemos cotas complexas a priori para pares suficientemente renormalizáveis com combinatória limitada e então a utilizamos para mostrar que quando o expoente crítico ? está próximo de um número par, o operador de renormalização tem um único ponto fixo, o qual é hiperbólico e possui uma variedade estável de codimensão um que contém todos os pares infinitamente renormalizáveis / We study the dynamics of the renormalization operator acting on the space of pairs (?, t), where ? is a diffeomorphism and t ? [0, 1], interpretated as unimodal maps ? o qt, where qt(x) = -2t|x|? + 2t - 1. We prove the so called complex bounds for sufficiently renormalizable pairs with bounded combinatorics. This allows us to show that if the critical exponent ? is close to an even number then the renormalization operator has a unique fixed point. Furthermore this fixed point is hyperbolic and its codimension one stable manifold contains all infinitely renormalizable pairs

Nós estudamos a dinâmica do operador de renormalização atuando no espaço de pares (?, t), onde ? é um difeomorfismo e t ? [0, 1], interpretados como aplicações unimodais ? o qt, onde qt(x) = -2t|x|? + 2t - 1. Estabelecemos cotas complexas a priori para pares suficientemente renormalizáveis com combinatória limitada e então a utilizamos para mostrar que quando o expoente crítico ? está próximo de um número par, o operador de renormalização tem um único ponto fixo, o qual é hiperbólico e possui uma variedade estável de codimensão um que contém todos os pares infinitamente renormalizáveis / We study the dynamics of the renormalization operator acting on the space of pairs (?, t), where ? is a diffeomorphism and t ? [0, 1], interpretated as unimodal maps ? o qt, where qt(x) = -2t|x|? + 2t - 1. We prove the so called complex bounds for sufficiently renormalizable pairs with bounded combinatorics. This allows us to show that if the critical exponent ? is close to an even number then the renormalization operator has a unique fixed point. Furthermore this fixed point is hyperbolic and its codimension one stable manifold contains all infinitely renormalizable pairs

This thesis proposes a new method to compute the lower and upper bounds of solution to the generalized Lyapunov matrix equation. Convergence of the iteratively computed bounds is illustrated by several numerical examples. Moreover, regularization of the condition required in computing the upper bound is also investigated. Finally, the method is employed to derive a less conservative bound on the magnitude of perturbation without destroying the stability of the perturbed system. All the theoretical results are verified by the numerical examples.

We study a generalization of the problem of finding bounds on the number of discrete chains, which itself is a generalization of the Erdős unit distance problem. Given a set of points in Euclidean space and a tree graph consisting of a much smaller number of vertices, we study the maximum possible number of tree graphs which can be represented by a prescribed tree graph. We derive an algorithm for finding tight bounds for this family of problems up to chain bound discrepancy, and give upper and lower bounds in special cases. / Master of Science / We study a generalization of the problem of finding bounds on the number of discrete chains, which itself is a generalization of the Erdős unit distance problem, a famous mathematics problem named after mathematician Paul Erdős. Given a set of points, and a tree graph of a much smaller amount of vertices, we study the maximum possible number of tree graphs which can be represented by a prescribed tree graph. We derive an algorithm for finding tight bounds for this family of problems up to chain bound discrepancy, and give upper and lower bounds in special cases.

Systems involving quantisation arise in many areas of engineering, especially when digital implementations are involved. In this thesis we consider different aspects of quantisation in feedback control systems. We study two topics of interest: (a) quantisers that quadratically stabilise a given system and are efficient in the use of their quantisation levels and (b) the derivation of ultimate bounds for perturbed systems, especially when the perturbations arise from the use of quantisers. In the first part of the thesis we address problem (a) above. We consider quadratic stabilisation of discrete-time multiple-input systems by means of quantised static feedback and we measure the efficiency of a quantiser via the concept of quantisation density. Intuitively, the lower the density of a quantiser is, the more separated its quantisation levels are. We thus deal with the problem of optimising density over all quantisers that quadratically stabilise a given system with respect to a given control Lyapunov function. Most of the available results on this problem treat single-input systems, and the ones that deal with the multiple-input case consider only two-input systems. In this thesis, we derive several new results for multiple-input systems and also provide an alternative approach to deal with the single-input case. Our new results for multiple-input systems include the derivation of the structure of optimal quantisers and the explicit design of multivariable quantisers with finite density that are able to quadratically stabilise systems having an arbitrary number of inputs. For single-input systems, we provide an alternative approach to the analysis and design of optimal quantisers by establishing a link between the separation of the quantisation levels of a quantiser and the size of its quantisation regions. In the second part of the thesis we address problem (b) above. In the presence of perturbations, asymptotic stabilisation may not be possible. However, there may exist a bounded region that contains the equilibrium point and has the property that the system trajectories converge to this bounded region. When this bounded region exists, we say that the system trajectories are ultimately bounded, and that this bounded region is an ultimate bound for the system. The size of the ultimate bound quantifies the performance of the system in steady state. Hence, it is important to derive ultimate bounds that are as tight as possible. This part of the thesis addresses the problem of ultimate bound computation in settings involving several scalar quantisers, each having different features. We consider each quantised variable in the system to be a perturbed copy of the corresponding unquantised variable. This turns the original quantised system into a perturbed system, where the perturbation has a natural \emph{componentwise} bound. Moreover, according to the type of quantiser employed, the perturbation bound may depend on the system state. Typical methods to estimate ultimate bounds are based on the use of Lyapunov functions and usually require a bound on the norm of the perturbation. Applying these methods in the setting considered here may disregard important information on the structure of the perturbation bound. We therefore derive ultimate bounds on the system states that explicitly take account of the componentwise structure of the perturbation bound. The ultimate bounds derived also have a componentwise form, and can be systematically computed without having to, e.g. select a suitable Lyapunov function for the system. The results of this part of the thesis, though motivated by quantised systems, apply to more general perturbations, not necessarily arising from quantisation. / PhD Doctorate

This thesis is intended to provide several new bounding techniques for channel codes over quasi-static fading channels (QSFC). This type of channel has drawn more and more attention recently with the demanding need for higher capacity and more reliable wireless communication systems. Although there have been some published results on analyzing the performance of channel codes over QSFCs, most of them produced quite loose performance upper bounds. In this thesis, the general Gallager bounding approach which provides convergent upper bounds of coded systems over QSFCs is addressed first. It is shown that previous Gallager bounds employing trivial low SNR bounds tended to be quite loose. Then improved low instantaneous SNR bounds are derived for two classes of convolutional codes including turbo codes. Consequently, they are combined with the classical Union-Chernoff bound to produce new performance upper bounds for simple convolutional and turbo codes over single-input single-output (SISO) QSFCs. The new bound provides a much improved alternative to characterizing the performance of channel codes over QSFCs over the existing ones. Next the new bounding approach is extended to cases of serially concatenated space-time block codes, which show equivalence with SISO QSFCs. Tighter performance bounds are derived for this coding scheme for two specific cases: first a convolutional code, and later a turbo code. Finally, the more challenging cases of multiple-input multiple-output (MIMO) QSFCs are investigated. Several performance upper bounds are derived for the bit error probability of different cases of space-time trellis codes (STTC) over QSFCs using a new and tight low SNR bound. Also included in this work is an algorithm for computing the unusual information eigenvalue spectrum of STTCs.

The most popular class of quantum error correcting codes is stabilizer codes. Binary quantum stabilizer codes have been well studied, and Calderbank, Rains, Shor and Sloane (July 1998) have constructed a table of upper bounds on the minimum distance of these codes using linear programming methods. However, not much is known in the case of nonbinary stabilizer codes. In this thesis, we establish a bridge between selforthogonal classical codes over the finite field containing q2 elements and quantum codes, extending and unifying previous work by Matsumoto and Uyematsu (2000), Ashikhmin and Knill (November 2001), Kim and Walker (2004). We construct a table of upper bounds on the minimum distance of the stabilizer codes using linear programming methods that are tighter than currently known bounds. Finally, we derive code construction techniques that will help us find new codes from existing ones. All these results help us to gain a better understanding of the theory of nonbinary stabilizer codes.

Iterative decoding and codes on graphs were first devised by Gallager in 1960, and then rediscovered by Berrou, Glavieux and Thitimajshima in 1993. This technique plays an important role in modern communications, especially in coding theory and practice. In particular, low-density parity-check (LDPC) codes, introduced by Gallager in the 1960s, are the class of codes at the heart of iterative coding. Since these codes are quite general and exhibit good performance under message-passing decoding, they play an important role in communications research today. A thorough analysis of iterative decoding systems and the relationship between maximum a posteriori (MAP) and belief propagation (BP) decoding was initiated by Measson, Montanari, and Urbanke. This analysis is based on density evolution (DE), and extrinsic information transfer (EXIT) functions, introduced by ten Brink. Following their work, this thesis considers the MAP decoding thresholds of three iterative decoding systems. First, irregular repeat-accumulate (IRA) and accumulaterepeataccumulate (ARA) code ensembles are analyzed on the binary erasure channel (BEC). Next, the joint iterative decoding of LDPC codes is studied on the dicode erasure channel (DEC). The DEC is a two-state intersymbol-interference (ISI) channel with erasure noise, and it is the simplest example of an ISI channel with erasure noise. Then, we introduce a slight generalization of the EXIT area theorem and apply the MAP threshold bound for the joint decoder. Both the MAP and BP erasure thresholds are computed and compared with each other. The result quantities the loss due to iterative decoding Some open questions include the tightness of these bounds and the extensions to non-erasure channels.