Abstract: Sturm's famous theorem (1829/35) provides an elegant algorithm to count and locate the real roots of any given real polynomial. In his residue calculus of complex functions, Cauchy (1831/37) assimilated this to an algebraic method to count and locate the complex roots of any given complex polynomial. We give a real-algebraic proof of Cauchy's theorem starting from the mere axioms of a real closed field, without appeal to analysis. This allows us to algebraicize Gauss' geometric argument (1799) and thus to derive a real-algebraic proof of the Fundamental Theorem of Algebra, stating that every complex polynomial of degree n has precisely n complex roots. The proof is elementary inasmuch as it uses only the intermediate value theorem and arithmetic of real polynomials. It can thus be formulated in the first-order language of real closed fields. Moreover, the proof is constructive and immediately translates to an algebraic root finding algorithm. The latter is sufficiently efficient for moderately sized polynomials, but in its present form it still lags behind Schönhage's nearly optimal numerical algorithm (1982).

Format: pdf, ps, ps.gz, English, 32 pages, 3 figures.
Annotated student version: pdf, ps, ps.gz, 38 pages.

Back to the roots – 19th century sources:
Gauss: Werke, Band 3, Dissertation (1799), English translation
Cauchy: Œuvres, Calcul des résidus (1831), Calcul des indices (1837)
Sturm: Mémoire sur la résolution des équations numériques (1835)
Sturm & Liouville: Démonstration d'un théorème de M. Cauchy (1836)
Ullherr: Existenz der Wurzeln der höhern algebraischen Gleichungen (1846)
Serret: Cours d'Algèbre supérieure (1877), archive, Théorème de Cauchy
Meyer (ed.): Encyklopädie der mathematischen Wissenschaften (1898), Band I.1
Molk (ed.): Encyclopédie des sciences mathématiques (1907), volume I.2

This is a continuation of my article Yang-Baxter deformations of quandles and racks, extending the results to the modular case.

Abstract: In his study of quantum groups, Drinfeld pointed out that every rack Q provides a set-theoretic solution c of the Yang-Baxter equation. This article examines the deformation theory of c within the space of Yang-Baxter operators, a problem initiated by Freyd and Yetter in 1989. Yang-Baxter deformations over a complete ring A are classified by Yang-Baxter cohomology. In the case of the set-theoretic operator c we show that the general Yang-Baxter cohomology complex retracts to a much smaller subcomplex, called quasi-diagonal. This greatly simplifies the deformation theory of c over A, including the modular case which had previously been left in suspense, by establishing that every deformation of c is gauge-equivalent to a quasi-diagonal one. In a quasi-diagonal deformation only behaviourally equivalent elements of Q interact; in the extreme case, where all elements of Q are behaviourally distinct, Yang-Baxter cohomology thus collapses to its diagonal part, which we identify with rack cohomology. This establishes a strong relationship between the classical deformation theory following Gerstenhaber and the more recent cohomology theory of racks, both of which have numerous applications in knot theory.

Format: pdf, ps, ps.gz, English, 26 pages, a few figures.

Abstract: Motivated by the study of ribbon knots we explore symmetric unions, a beautiful construction introduced by Kinoshita and Terasaka in 1957. We develop a two-variable refinement W_D(s,t) of the Jones polynomial that is invariant under symmetric Reidemeister moves. If D is a symmetric union diagram, representing a ribbon knot K, then the polynomial W_D(s,t) nicely reflects their topological properties. In particular it elucidates the connection between the Jones polynomials of K and its partial knots K_±: we obtain W_D(t,t) = V_K(t) and W_D(-1,t) = V_K-(t) V_K+(t), which has the form f(t) f(1/t) reminiscent of the Alexander polynomial of ribbon knots.

Format: pdf, ps, ps.gz, English, 26 pages, many figures.

Abstract: This article establishes the algebraic covering theory of quandles. For every connected quandle we explicitly construct a universal covering, which in turn leads us to define the algebraic fundamental group as the automorphism group of the universal covering. We then establish the Galois correspondence between connected coverings and subgroups of the fundamental group. Quandle coverings are thus formally analogous to coverings of topological spaces, and resemble Kervaire's algebraic covering theory of perfect groups. A detailed investigation also reveals some crucial differences, which we illustrate by numerous examples.

As an application we obtain a simple formula for the second (co)homology group of a quandle Q. It has long been known that H₁(Q) = H¹(Q) = Z[\pi₀(Q)], and we construct natural isomorphisms H₂(Q) = \pi₁(Q,q)_ab and H²(Q,A) = Ext(Q,A) = Hom(\pi₁(Q,q),A), reminiscent of the classical Hurewicz isomorphisms in degree 1. This means that whenever the fundamental group is known, (co)homology calculations in degree 2 become very easy.

Format: pdf, ps, ps.gz, English, 48 pages, 2 figures.

Abstract: This article explicitly constructs and classifies all arrovian voting systems on three or more alternatives. If we demand orderings to be complete, we have, of course, Arrow's classical dictator theorem, and a closer look reveals the classification of all such voting systems as dictatorial hierarchies.

If we leave the traditional realm of complete orderings, the picture changes. Here we consider the more general setting where alternatives may be incomparable, that is, we allow orderings that are reflexive and transitive but not necessarily complete. Instead of a dictator we exhibit a junta whose internal hierarchy or coalition structure can be surprisingly rich. As a universal tool for studying this fine structure of arrovian voting systems we introduce and develop the notion of a relatively decisive set of voters. This allows us to give an explicit description of all such voting systems, generalizing and unifying various previous results.

Format: pdf, ps, ps.gz, English, 23 pages, 1 figure.

Abstract: For every n-component ribbon link L we prove that the Jones polynomial V(L) is divisible by the polynomial V(Oⁿ) of the trivial link. This integrality property allows us to define a generalized determinant det V(L) := [V(L)/V(Oⁿ)]_(t=-1), for which we derive congruences reminiscent of the classical Arf invariant: every ribbon link L = K₁ ∪ ... ∪ K_n satisfies det V(L) = det(K₁) ... det(K_n) modulo 32, and in particular det V(L) = 1 modulo 8.

These results motivate to study the power series expansion V(L) = Σ d_k(L) h^k at t=-1, instead of t=1 as usual. We obtain a family of link invariants d_k(L), starting with the link determinant d₀(L) = det(L) obtained from a Seifert surface S spanning L. The invariants d_k(L) are not of finite type with respect to crossing changes of L, but they turn out to be of finite type with respect to band crossing changes of S. This discovery is the starting point of a theory of surface invariants of finite type, which promises to reconcile quantum invariants with the theory of Seifert surfaces, or more generally ribbon surfaces.

Format: pdf, ps, ps.gz, English, 38 pages, many figures.

Abstract: Solutions of a diophantine equation f(a,b)=g(c,d), with a,b,c,d in some finite range, can be efficiently enumerated by sorting the values of f and g in ascending order and searching for collisions.

This article considers functions f that are bimonotone in the sense that f(a,b) ≤ f(a',b') whenever a ≤ a' and b ≤ b'. A two-variable polynomial with non-negative coefficients is a typical example. The problem is to efficiently enumerate all pairs (a,b) such that the values f(a,b) appear in increasing order.

We present an algorithm that is memory-efficient and highly parallelizable. In order to enumerate the first n values of f, the algorithm only builds up a priority queue of length at most √(2n)+1. In terms of bit-complexity this ensures that the algorithm takes time O(n log²n) and requires memory O(n^½ log n), which considerably improves on the memory bound Θ(n log n) provided by a naive approach, and extends the semimonotone enumeration algorithm previously considered by R.L. Ekl and D.J. Bernstein.

Format: pdf, ps, ps.gz, English, 22 pages, 7 figures.

Software: An implementation in C++ is available for download.

Abstract: We present an intriguing question about lattice points in triangles where Pick's formula is "almost correct". The question has its origin in knot theory, but its statement is purely combinatorial. After more than 30 years the topological question has been solved recently but the lattice point problem is still open.

Format: pdf, ps, ps.gz, English, 6 pages.

Software: An implementation in C++ is available for download.

Abstract: Motivated by the study of ribbon knots we explore symmetric unions, a beautiful construction introduced by Kinoshita and Terasaka 50 years ago. It is easy to see that every symmetric union represents a ribbon knot, but the converse is still an open problem. Besides existence it is natural to consider the question of uniqueness. In order to attack this question we extend the usual Reidemeister moves to a family of moves respecting the symmetry, and consider the symmetric equivalence thus generated. This notion being in place, we discuss several situations in which a knot can have essentially distinct symmetric union representations. We exhibit an infinite family of ribbon two-bridge knots each of which allows two different symmetric union representations.

Format: pdf, ps, ps.gz, English, 19 pages, 20 figures.

Abstract: This article introduces a natural extension of colouring numbers of knots, called colouring polynomials, and studies their relationship to Yang-Baxter invariants and quandle 2-cocycle invariants.

For a knot K in the 3-sphere let G(K) be the fundamental group of the knot complement, and let m(K), l(K) be a meridian-longitude pair in G(K). Given a finite group G and an element x in G, we consider the set of representations r of G(K) to G that map the meridian m(K) to x, and define the colouring polynomial P(K) as the sum over all longitude images r(l(K)). The resulting invariant maps knots to the group ring ZG. It is multiplicative with respect to connected sum and equivariant with respect to symmetry operations of knots. Examples are given to show that colouring polynomials distinguish knots for which other invariants fail, in particular they can distinguish knots from their obverses, inverses, or reverses.

We prove that every quandle 2-cocycle state-sum invariant of knots is a specialization of some knot colouring polynomial. This provides a complete topological interpretation of these invariants in terms of the knot group and its peripheral system. Furthermore, we show that every knot colouring polynomial can be presented as a Yang-Baxter invariant, i.e. as the trace of some linear braid group representation. This entails in particular that Yang-Baxter invariants can detect non-inversible and non-reversible knots.

Format: pdf, ps, ps.gz, English, 24 pages, 6 figures

Abstract: Given a rack Q and a ring A, one can construct a Yang-Baxter operator c on V tensor V, where V = AQ is the free A-module with basis Q, by setting c(x tensor y) = y tensor x^y for all x,y in Q. In answer to a question initiated by D.N. Yetter and P.J. Freyd, this article classifies formal deformations of c in the space of Yang-Baxter operators. For the trivial rack, where x^y = x for all x,y, one has, of course, the classical setting of r-matrices and quantum groups. In the general case we introduce and calculate the cohomology theory that classifies infinitesimal deformations of c. In many cases this allows us to conclude that c is rigid. In the remaining cases, where infinitesimal deformations are possible, we show that higher-order obstructions are the same as in the quantum case.

Format: pdf, ps, ps.gz, English, 26 pages, several figures.

Abstract: This article examines relations between 3-manifold topology and knot invariants of finite type. We prove that in every Whitehead manifold there exist knots that cannot be distinguished by Vassiliev invariants. If, on the other hand, Vassiliev invariants distinguish knots in each homotopy sphere, then the Poincaré conjecture is true (i.e. every homotopy sphere is homeomorphic to the standard sphere).

Format: pdf, ps, ps.gz, English, 16 pages, 6 figures.

Abstract: A classical theorem of R.H. Bing states that a closed connected 3-manifold M is homeomorphic to the 3-sphere if and only if every knot in M is contained in a 3-ball. We give a simple proof of this characterization based on the surgery presentation of 3-manifolds.

Format: pdf, ps, ps.gz, English, 3 pages, 1 figure.

Abstract: Given a knot K in the 3-sphere, let Q_K be its fundamental quandle as introduced by D.Joyce. Its first homology group is easily seen to be H₁(Q_K)=Z. We prove that H₂(Q_K)=0 if and only if K is trivial, and H₂(Q_K)=Z whenever K is non-trivial. An analogous result holds for links, thus characterizing trivial components. More detailed information can be derived from the conjugation quandle: let Q'_K be the conjugacy class of a meridian in the knot group. We show that H₂(Q'_K)=Z^p, where p is the number of prime summands in a connected sum decomposition of K.

Format: pdf, ps, ps.gz, English, 22 pages, 3 figures.

Abstract: It is a well-known paradigm to consider Vassiliev invariants as polynomial functions on the set of knots. We prove the following characterization: a rational knot invariant is a Vassiliev invariant of degree <m if and only if it is a polynomial of degree <m on every geometric sequence of knots. Here a sequence K(z) is called geometric if the knots K(z) coincide outside a ball B, inside of which they correspond to a geometric sequence of braids, t^z, for all z and some pure braid t.

As an application we show that the torsion in the braid group over the sphere induces torsion at the level of Vassiliev invariants: there exist knots in S¹xS² that can be distinguished by Z₂-invariants of finite type but not by rational invariants of finite type. In order to obtain such torsion invariants we construct over Z a universal Vassiliev invariant of degree 1 for knots in S¹xS².

Format: pdf, ps, ps.gz, English, 21 pages, 9 figures.

Abstract: We prove the following result: if Vassiliev invariants distinguish knots in each homotopy sphere, then the Poincaré conjecture is true, in other words every homotopy sphere is homeomorphic to the standard sphere. On the other hand, in every Whitehead manifold there exist knots that cannot be distinguished by Vassiliev invariants.

Format: pdf, ps, ps.gz, French, 6 pages including 1½ pages of an abridged English version.

Abstract: We introduce geometric sequences of knots and establish the following criterion: if v is a rational invariant of degree <m in the sense of Vassiliev then v is a polynomial of degree <m on every geometric sequence of knots. The torsion in the braid group over the sphere induces torsion at the level of Vassiliev invariants: we construct knots in S²xS¹ which cannot be distinguished by rational invariants of finite type. They can, however, be distinguished by invariants of finite type with values in a finite abelian group.

Format: pdf, ps, ps.gz, French, 5 pages including 1½ pages of an abridged English version, 1 figure.

Abstract: For a finite group G and a knot K in the 3-sphere, let F(K) be the number of representations of the knot group into G. In answer to a question of D. Altschuler we show that F is either constant or not of finite type. Moreover, F is constant if and only if G is nilpotent. We prove the following, more general boundedness theorem: if a knot invariant F is bounded by some function of the braid index, the genus, or the unknotting number, then F is either constant or not of finite type.

Format: pdf, ps, ps.gz, English, 7 pages, 3 figures.

Résumé : En 1984 Jones découvrit son invariant polynomial, qui ne ressemblait à aucun concept connu auparavant. En quelques années cette découverte a provoqué l'invention de nombreux autres invariants polynomiaux et des invariants dits quantiques ou de type fini, issus des représentations du groupe des tresses et souvent inspirés par des analogies avec la physique théorique. Malgré leurs mérites pour la théorie des nœuds et des 3-variétés, ces invariants restent peu compris du coté de la topologie algébrique, et parfois de la topologie tout court. Ce mémoire présente et discute quelques éléments de réponse.

Abstract: In 1984 Jones discovered a polynomial invariant of knots which resembled none of the formerly known concepts. Within a few years this led to the invention of a multitude of other polynomial invariants, also called quantum invariants or invariants of finite type, coming from braid group representations and often inspired by analogies with theoretical physics. Despite their merits for knot theory and the theory of 3-manifolds, these invariants remain ill understood from the viewpoint of algebraic topology or 3-dimensional topology. This mémoire presents and discusses some partial answers.

Format: pdf, ps, ps.gz, French, 43 pages.

Format: pdf, ps, ps.gz, German, 133 pages.

Résumé : Depuis plus d’une décennie Google domine le marché des moteurs de recherche sur internet. Son point fort est qu’il trie intelligemment ses résultats par ordre de pertinence. Comment est-ce possible ? Depuis sa conception en 1998, Google continue à évoluer et la plupart des améliorations demeurent des secrets bien gardés. L’idée principale, par contre, a été publiée : le pilier de son succès est une judicieuse modélisation mathématique que nous retraçons ici.

Format: pdf, French, 4 pages, annexe de 4 pages d'approfondissement.

Résumé : Ce document est issu du stage « modélisation, recherche, preuve » mis au point par l'Institut de Recherche sur l'Enseignement des Mathématiques (IREM / Institut Fourier, UJF Grenoble) durant l'année 2008/2009 dans le plan académique de formation des enseignants (PAF).

Ce stage ouvre avec un atelier sur la construction à la règle et au compas, un sujet qui fascine depuis l'antiquité et qui reste très présent dans l'éducation mathématique. Sur le plan pratique, il est intéressant de savoir comment construire certaines configurations concrètement. Sur le plan théorique, il est intéressant de savoir quelles sont les constructions possibles, ou dans le cas contraire lesquelles sont impossibles et pourquoi.

Nous en discutons trois problèmes célèbres, pour lesquels ce document veut servir de support: la construction de polygones réguliers, la duplication du volume d'un cube, la trisection de l'angle. Avec un peu de persévérance ces problèmes sont résolubles par des outils parfaitement élémentaires, mobilisant des connaissances variées de niveau lycée.

Format: pdf, French, 12 pages.

Résumé : Le point fort du moteur de recherche Google est qu'il trie intelligemment ses résultats par ordre d'importance. Nous expliquons ici l'algorithme PageRank qui est à la base de ce classement. Il faut d'abord établir un modèle qui permet de définir ce que l'on entend par « importance ». Une fois ce modèle formalisé, il s'agit de résoudre astucieusement un immense système d'équations linéaires.

Il va sans dire que l'application pratique est devenue très importante. Bien qu'élémentaires, les arguments mathématiques sous-jacents n'en sont pas moins intéressants: l'approche fait naturellement intervenir l'algèbre linéaire, la « marche aléatoire » sur un graphe et le théorème du point fixe. Tout ceci en fait un très beau sujet pour la culture des mathématiques et leurs applications.

Format: pdf, ps, ps.gz, French, 15 pages.

Résumé : Des nœuds, des tresses, et d'autres objets noués apparaissent non seulement dans la vie quotidienne, la marine et l'art décoratif, mais aussi en sciences. En biologie moléculaire, par exemple, l'ADN peut être noué, et généralement il l'est. En physique, certains modèles quantiques font apparaître des structures qui ressemblent à des tresses. En mathématiques, finalement, l'étude des nœuds sert à comprendre les espaces de dimension 3. Même à un niveau élémentaire le sujet révèle une richesse surprenante...

Format: pdf, ps, ps.gz, French, 2 pages.