Mathematical English (A Brief Summary) PDF

Mathematical English (a brief summary) Jan Nekovář Université Paris 6 c Jan Nekovář 2011 1  Arithmetic Integers 0 zero...

Mathematical English (a brief summary) Jan Nekovář Université Paris 6 c Jan Nekovář 2011 1  Arithmetic Integers 0 zero 10 ten 20 twenty 1 one 11 eleven 30 thirty 2 two 12 twelve 40 forty 3 three 13 thirteen 50 fifty 4 four 14 fourteen 60 sixty 5 five 15 fifteen 70 seventy 6 six 16 sixteen 80 eighty 7 seven 17 seventeen 90 ninety 8 eight 18 eighteen 100 one hundred 9 nine 19 nineteen 1000 one thousand −245 minus two hundred and forty-five 22 731 twenty-two thousand seven hundred and thirty-one 1 000 000 one million 56 000 000 fifty-six million 1 000 000 000 one billion [US usage, now universal] 7 000 000 000 seven billion [US usage, now universal] 1 000 000 000 000 one trillion [US usage, now universal] 3 000 000 000 000 three trillion [US usage, now universal] Fractions [= Rational Numbers] 1 3 2 one half 8 three eighths 1 26 3 one third 9 twenty-six ninths 1 5 4 one quarter [= one fourth] − 34 minus five thirty-fourths 1 5 one fifth 2 73 two and three sevenths 1 − 17 minus one seventeenth Real Numbers −0.067 minus nought point zero six seven 81.59 eighty-one point five nine −2.3 · 106 minus two point three times ten to the six [= −2 300 000 minus two million three hundred thousand] 4 · 10−3 four times ten to the minus three [= 0.004 = 4/1000 four thousandths] π [= 3.14159...] pi [pronounced as ‘pie’] e [= 2.71828...] e [base of the natural logarithm] 2  Complex Numbers i i 3 + 4i three plus four i 1 − 2i one minus two i 1 − 2i = 1 + 2i the complex conjugate of one minus two i equals one plus two i The real part and the imaginary part of 3 + 4i are equal, respectively, to 3 and 4. Basic arithmetic operations Addition: 3+5=8 three plus five equals [= is equal to] eight Subtraction: 3 − 5 = −2 three minus five equals [=... ] minus two Multiplication: 3 · 5 = 15 three times five equals [=... ] fifteen Division: 3/5 = 0.6 three divided by five equals [=... ] zero point six (2 − 3) · 6 + 1 = −5 two minus three in brackets times six plus one equals minus five 1−3 2+4 = −1/3 one minus three over two plus four equals minus one third 4! [= 1 · 2 · 3 · 4] four factorial Exponentiation, Roots 52 [= 5 · 5 = 25] five squared 53 [= 5 · 5 · 5 = 125] five cubed 54 [= 5 · 5 · 5 · 5 = 625] five to the (power of) four 5−1 [= 1/5 = 0.2] five to the minus one −2 5√ [= 1/52 = 0.04] five to the minus two √ 3 [= 1.73205...] the square root of three 3 √ 64 [= 4] the cube root of sixty four 5 32 [= 2] the fifth root of thirty two √ In the complex domain the notation n a is √ ambiguous, since any non-zero complex number has n different n-th roots. For example, 4 −4 has four possible values: ±1 ± i (with all possible combinations of signs). (1 + 2)2+2 one plus two, all to the power of two plus two eπi = −1 e to the (power of) pi i equals minus one Divisibility The multiples of a positive integer a are the numbers a, 2a, 3a, 4a,.... If b is a multiple of a, we also say that a divides b, or that a is a divisor of b (notation: a | b). This is equivalent to ab being an integer. 3  Division with remainder If a, b are arbitrary positive integers, we can divide b by a, in general, only with a remainder. For example, 7 lies between the following two consecutive multiples of 3:   7 1 2 · 3 = 6 < 7 < 3 · 3 = 9, 7=2·3+1 ⇐⇒ =2+. 3 3 In general, if qa is the largest multiple of a which is less than or equal to b, then b = qa + r, r = 0, 1,... , a − 1. The integer q (resp., r) is the quotient (resp., the remainder) of the division of b by a. Euclid’s algorithm This algorithm computes the greatest common divisor (notation: (a, b) = gcd(a, b)) of two positive integers a, b. It proceeds by replacing the pair a, b (say, with a ≤ b) by r, a, where r is the remainder of the division of b by a. This procedure, which preserves the gcd, is repeated until we arrive at r = 0. Example. Compute gcd(12, 44). 44 = 3 · 12 + 8 12 = 1 · 8 + 4 gcd(12, 44) = gcd(8, 12) = gcd(4, 8) = gcd(0, 4) = 4. 8=2·4+0 44 This calculation allows us to write the fraction 12 in its lowest terms, and also as a continued fraction: 44 44/4 11 1 = = =3+. 12 12/4 3 1 1+ 2 If gcd(a, b) = 1, we say that a and b are relatively prime. add additionner algorithm algorithme Euclid’s algorithm algorithme de division euclidienne bracket parenthèse left bracket parenthèse à gauche right bracket parenthèse à droite curly bracket accolade denominator denominateur 4 difference différence divide diviser divisibility divisibilité divisor diviseur exponent exposant factorial factoriel fraction fraction continued fraction fraction continue gcd [= greatest common divisor] pgcd [= plus grand commun diviseur] lcm [= least common multiple] ppcm [= plus petit commun multiple] infinity l’infini iterate itérer iteration itération multiple multiple multiply multiplier number nombre even number nombre pair odd number nombre impair numerator numerateur pair couple pairwise deux à deux power puissance product produit quotient quotient ratio rapport; raison rational rationnel(le) irrational irrationnel(le) relatively prime premiers entre eux remainder reste root racine sum somme subtract soustraire 5  Algebra Algebraic Expressions A = a2 capital a equals small a squared a=x+y a equals x plus y b=x−y b equals x minus y c=x·y·z c equals x times y times z c = xyz c equals x y z (x + y)z + xy x plus y in brackets times z plus x y x2 + y 3 + z 5 x squared plus y cubed plus z to the (power of) five n n n x +y =z x to the n plus y to the n equals z to the n (x − y)3m x minus y in brackets to the (power of) three m x minus y, all to the (power of) three m 2x 3y two to the x times three to the y ax2 + bx + c a x squared plus b x plus c √ √ x+ 3y the square root of x plus the cube root of y √ n x+y the n-th root of x plus y a+b c−d a plus b over c minus d n
m (the binomial coefficient) n over m Indices x0 x zero; x nought x1 + yi x one plus y i Rij (capital) R (subscript) i j; (capital) R lower i j k Mij (capital) M upper k lower i j; (capital) M superscript k subscript i j Pn i=0 ai xi sum of a i x to the i for i from nought [= zero] to n; sum over i (ranging) from zero to n of a i (times) x to the i Q∞ m=1 bm product of b m for m from one to infinity; product over m (ranging) from one to infinity of b m Pn j=1 aij bjk sum of a i j times b j k for j from one to n; sum over j (ranging) from one to n of a i j times b j k Pn n
i=0 i xi y n−i sum of n over i x to the i y to the n minus i for i from nought [= zero] to n 6  Matrices column colonne column vector vecteur colonne determinant déterminant index (pl. indices) indice matrix matrice matrix entry (pl. entries) coefficient d’une matrice m × n matrix [m by n matrix] matrice à m lignes et n colonnes multi-index multiindice row ligne row vector vecteur ligne square carré square matrix matrice carrée Inequalities x>y x is greater than y x≥y x is greater (than) or equal to y x0 x is positive x≥0 x is positive or zero; x is non-negative xy x est strictement plus grand que y x≥y x est supérieur ou égal à y x0 x est strictement positif x≥0 x est positif ou nul x 0, then x1 6= x2 are both real; if ∆ < 0, then x1 = x2 are complex conjugates of each other (and non-real). coefficient coefficient degree degré discriminant discriminant equation équation L.H.S. [= left hand side] terme de gauche R.H.S. [= right hand side] terme de droite polynomial adj. polynomial(e) polynomial n. polynôme provided that à condition que root racine simple root racine simple double root racine double triple root racine triple multiple root racine multiple root of multiplicity m racine de multiplicité m 8 solution solution solve résoudre Congruences Two integers a, b are congruent modulo a positive integer m if they have the same remainder when divided by m (equivalently, if their difference a − b is a multiple of m). a ≡ b (mod m) a is congruent to b modulo m a ≡ b (m)  Some people use the following, slightly horrible, notation: a = b [m]. Fermat’s Little Theorem. If p is a prime number and a is an integer, then ap ≡ a (mod p). In other words, ap − a is always divisible by p. Chinese Remainder Theorem. If m1 ,... , mk are pairwise relatively prime integers, then the system of congruences x ≡ a1 (mod m1 ) ··· x ≡ ak (mod mk ) has a unique solution modulo m1 · · · mk , for any integers a1 ,... , ak.  The definite article (and its absence) measure theory théorie de la mesure number theory théorie des nombres Chapter one le chapitre un Equation (7) l’équation (7) Harnack’s inequality l’inégalité de Harnack the Harnack inequality the Riemann hypothesis l’hypothèse de Riemann the Poincaré conjecture la conjecture de Poincaré Minkowski’s theorem le théorème de Minkowski the Minkowski theorem the Dirac delta function la fonction delta de Dirac Dirac’s delta function the delta function la fonction delta 9  Geometry D C E A B Let E be the intersection of the diagonals of the rectangle ABCD. The lines (AB) and (CD) are parallel to each other (and similarly for (BC) and (DA)). We can see on this picture several acute angles: 6 EAD, 6 EAB, 6 EBA, 6 AED, 6 BEC... ; right angles: 6 ABC, 6 BCD, 6 CDA, 6 DAB and obtuse angles: 6 AEB, 6 CED. e Q r P R Let P and Q be two points lying on an ellipse e. Denote by R the intersection point of the respective tangent lines to e at P and Q. The line r passing through P and Q is called the polar of the point R w.r.t. the ellipse e. 10 Here we see three concentric circles with respective radii equal to 1, 2 and 3. If we draw a line through each vertex of a given triangle and the midpoint of the opposite side, we obtain three lines which intersect at the barycentre (= the centre of gravity) of the triangle. Above, three circles have a common tangent at their (unique) intersection point. 11  Euler’s Formula Let P be a convex polyhedron. Euler’s formula asserts that V − E + F = 2, V = the number of vertices of P , E = the number of edges of P , F = the number of faces of P. Exercise. Use this formula to classify regular polyhedra (there are precisely five of them: tetrahedron, cube, octahedron, dodecahedron and icosahedron). For example, an icosahedron has 20 faces, 30 edges and 12 vertices. Each face is an isosceles triangle, each edge belongs to two faces and there are 5 faces meeting at each vertex. The midpoints of its faces form a dual regular polyhedron, in this case a dodecahedron, which has 12 faces (regular pentagons), 30 edges and 20 vertices (each of them belonging to 3 faces). angle angle acute angle angle aigu obtuse angle angle obtus right angle angle droit area aire axis (pl. axes) axe coordinate axis axe de coordonnées horizontal axis axe horisontal vertical axis axe vertical centre [US: center] centre circle cercle colinear (points) (points) alignés conic (section) (section) conique cone cône convex convexe cube cube curve courbe dimension dimension distance distance dodecahedron dodecaèdre edge arête ellipse ellipse ellipsoid ellipsoı̈de face face hexagon hexagone hyperbola hyperbole hyperboloid hyperboloı̈de 12  one-sheet (two-sheet) hyperboloid hyperboloı̈de à une nappe (à deux nappes) icosahedron icosaèdre intersect intersecter intersection intersection lattice réseau lettuce laitue length longeur line droite midpoint of milieu de octahedron octaèdre orthogonal; perpendicular orthogonal(e); perpendiculaire parabola parabole parallel parallèl(e) parallelogram parallélogramme pass through passer par pentagon pentagone plane plan point point (regular) polygon polygone (régulier) (regular) polyhedron (pl. polyhedra) polyèdre (régulier) projection projection central projection projection conique; projection centrale orthogonal projection projection orthogonale parallel projection projection parallèle quadrilateral quadrilatère radius (pl. radii) rayon rectangle rectangle rectangular rectangulaire rotation rotation side côté slope pente sphere sphère square carré square lattice réseau carré surface surface tangent to tangent(e) à tangent line droite tangente tangent hyper(plane) (hyper)plan tangent tetrahedron tetraèdre triangle triangle equilateral triangle triangle équilatéral isosceles triangle triangle isocèle right-angled triangle triangle rectangle vertex sommet 13  Linear Algebra basis (pl. bases) base change of basis changement de base bilinear form forme bilinéaire coordinate coordonnée (non-)degenerate (non) dégénéré(e) dimension dimension codimension codimension finite dimension dimension finie infinite dimension dimension infinie dual space espace dual eigenvalue valeur propre eigenvector vecteur propre (hyper)plane (hyper)plan image image isometry isométrie kernel noyau linear linéaire linear form forme linéaire linear map application linéaire linearly dependent liés; linéairement dépendants linearly independent libres; linéairement indépendants multi-linear form forme multilinéaire origin origine orthogonal; perpendicular orthogonal(e); perpendiculaire orthogonal complement supplémentaire orthogonal orthogonal matrix matrice orthogonale (orthogonal) projection projection (orthogonale) quadratic form forme quadratique reflection réflexion represent représenter rotation rotation scalar scalaire scalar product produit scalaire subspace sous-espace (direct) sum somme (directe) skew-symmetric anti-symétrique symmetric symétrique trilinear form forme trilinéaire vector vecteur vector space espace vectoriel vector subspace sous-espace vectoriel vector space of dimension n espace vectoriel de dimension n 14  Mathematical arguments Set theory x∈A x is an element of A; x lies in A; x belongs to A; x is in A x 6∈ A x is not an element of A; x does not lie in A; x does not belong to A; x is not in A x, y ∈ A (both) x and y are elements of A;... lie in A;... belong to A;... are in A x, y 6∈ A (neither) x nor y is an element of A;... lies in A;... belongs to A;... is in A ∅ the empty set (= set with no elements) A=∅ A is an empty set A 6= ∅ A is non-empty A∪B the union of (the sets) A and B; A union B A∩B the intersection of (the sets) A and B; A intersection B A×B the product of (the sets) A and B; A times B A∩B =∅ A is disjoint from B; the intersection of A and B is empty {x |...} the set of all x such that... C the set of all complex numbers Q the set of all rational numbers R the set of all real numbers A ∪ B contains those elements that belong to A or to B (or to both). A ∩ B contains those elements that belong to both A and B. A × B contains the ordered pairs (a, b), where a (resp., b) belongs to A (resp., to B). An = A × · · · × A contains all ordered n-tuples of elements of A. | {z } n times belong to appartenir à disjoint from disjoint de element élément empty vide non-empty non vide intersection intersection inverse l’inverse the inverse map to f l’application réciproque de f the inverse of f l’inverse de f map application bijective map application bijective injective map application injective surjective map application surjective pair couple 15  ordered pair couple ordonné triple triplet quadruple quadruplet n-tuple n-uplet relation relation equivalence relation relation d’équivalence set ensemble finite set ensemble fini infinite set ensemble infini union réunion Logic S ∨ T S or T S ∧ T S and T S =⇒ T S implies T; if S then T S ⇐⇒ T S is equivalent to T; S iff T ¬S not S ∀x ∈ A... for each [= for every] x in A... ∃x ∈ A... there exists [= there is] an x in A (such that)... ∃! x ∈ A... there exists [= there is] a unique x in A (such that)... 6∃x ∈ A... there is no x in A (such that)... x > 0 ∧ y > 0 =⇒ x + y > 0 if both x and y are positive, so is x + y 6 ∃ x ∈ Q x2 = 2 no rational number has a square equal to two ∀ x ∈ R ∃ y ∈ Q |x − y| < 2/3 for every real number x there exists a rational number y such that the absolute value of x minus y is smaller than two thirds Exercise. Read out the following statements. x ∈ A ∩ B ⇐⇒ (x ∈ A ∧ x ∈ B), x ∈ A ∪ B ⇐⇒ (x ∈ A ∨ x ∈ B), 2 2 ∀x ∈ R x ≥ 0, ¬∃ x ∈ R x < 0, ∀ y ∈ C ∃ z ∈ C y = z2. Basic arguments It follows from... that... We deduce from... that... Conversely,... implies that... Equality (1) holds, by Proposition 2. By definition,... 16 The following statements are equivalent. Thanks to... , the properties... and... of... are equivalent to each other.... has the following properties. Theorem 1 holds unconditionally. This result is conditional on Axiom A.... is an immediate consequence of Theorem 3. Note that... is well-defined, since... As... satisfies... , formula (1) can be simplified as follows. We conclude (the argument) by combining inequalities (2) and (3). (Let us) denote by X the set of all... Let X be the set of all... Recall that... , by assumption. It is enough to show that... We are reduced to proving that... The main idea is as follows. We argue by contradiction. Assume that... exists. The formal argument proceeds in several steps. Consider first the special case when... The assumptions... and... are independent (of each other), since...... , which proves the required claim. We use induction on n to show that... On the other hand,...... , which means that... In other words,... argument argument assume supposer assumption hypothèse axiom axiome case cas special case cas particulier claim v. affirmer (the following) claim l’affirmation suivante; l’assertion suivante concept notion conclude conclure conclusion conclusion condition condition a necessary and sufficient condition une condition nécessaire et suffisante conjecture conjecture 17 consequence conséquence consider considérer contradict contredire contradiction contradiction conversely réciproquement corollary corollaire deduce déduire define définir well-defined bien défini(e) definition définition equivalent équivalent(e) establish établir example exemple exercise exercice explain expliquer explanation explication false faux, fausse formal formel hand main on one hand d’une part on the other hand d’autre part iff [= if and only if ] si et seulement si imply impliquer, entraı̂ner induction on récurrence sur lemma lemme proof preuve; démonstration property propriété satisfy property P satisfaire à la propriété P ; vérifier la propriété P proposition proposition reasoning raisonnement reduce to se ramener à remark remarque(r) required réquis(e) result résultat s.t. = such that statement énoncé t.f.a.e. = the following are equivalent theorem théorème true vrai truth vérité wlog = without loss of generality word mot in other words autrement dit 18  Functions Formulas/Formulae f (x) f of x g(x, y) g of x (comma) y h(2x, 3y) h of two x (comma) three y sin(x) sine x cos(x) cosine x tan(x) tan x arcsin(x) arc sine x arccos(x) arc cosine x arctan(x) arc tan x sinh(x) hyperbolic sine x cosh(x) hyperbolic cosine x tanh(x) hyperbolic tan x sin(x2 ) sine of x squared sin(x)2 sine squared of x; sine x, all squared x+1 tan(y 4 ) x plus one, all over over tan of y to the four 3x−cos(2x) three to the (power of) x minus cosine of two x exp(x3 + y 3 ) exponential of x cubed plus y cubed Intervals (a, b) open interval a b [a, b] closed interval a b (a, b] half open interval a b (open on the left, closed on the right) [a, b) half open interval a b (open on the right, closed on the left)  The French notation is different! ]a, b[ intervalle ouvert a b [a, b] intervalle fermé a b ]a, b] intervalle demi ouvert a b (ouvert à gauche, fermé à droite) [a, b[ intervalle demi ouvert a b (ouvert à droite, fermé à gauche) Exercise. Which of the two notations do you prefer, and why? Derivatives f0 f dash; f prime; the first derivative of f 19  f 00 f double dash; f double prime; the second derivative of f (3) f the third derivative of f f (n) the n-th derivative of f dy dx d y by d x; the derivative of y by x d2 y dx2 the second derivative of y by x; d squared y by d x squared ∂f ∂x the partial derivative of f by x (with respect to x); partial d f by d x ∂ 2f ∂x2 the second partial derivative of f by x (with respect to x) partial d squared f by d x squared ∇f nabla f; the gradient of f ∆f delta f Example. The (total) differential of a function f (x, y, z) in three real variables is equal to ∂f ∂f ∂f df = dx + dy + dz. ∂x ∂y ∂z The gradient of f is the vector whose components are the partial derivatives of f with respect to the three variables:   ∂f ∂f ∂f ∇f = , ,. ∂x ∂y ∂z The Laplace operator ∆ acts on f by taking the sum of the second partial derivatives with respect to the three variables: ∂ 2f ∂ 2f ∂ 2f ∆f = + +. ∂x2 ∂y 2 ∂z 2 The Jacobian matrix of a pair of functions g(x, y), h(x, y) in two real variables is the 2 × 2 matrix whose entries are the partial derivatives of g and h, respectively, with respect to the two variables:  ∂g ∂g  ∂x ∂y ∂h ∂h. ∂x ∂y Integrals R f (x) dx integral of f of x d x Rb 2 a t dt integral from a to b of t squared d t RR S h(x, y) dx dy double integral over S of h of x y d x d y 20  Differential equations An ordinary (resp., a partial) differential equation, abbreviated as ODE (resp., PDE), is an equation involving an unknown function f of one (resp., more than one) variable together with its derivatives (resp., partial derivatives). Its order is the maximal order of derivatives that appear in the equation. The equation is linear if f and its derivatives appear linearly; otherwise it is non-linear. f 0 + xf = 0 first order linear ODE 00 f + sin(f ) = 0 second order non-linear ODE (x2 + y) ∂f ∂x − (x + y 2 ) ∂f ∂y + 1 = 0 first order linear PDE The classical linear PDEs arising from physics involve the Laplace operator ∂2 ∂2 ∂2 ∆= + +. ∂x2 ∂y 2 ∂z 2 ∆f = 0 the Laplace equation ∆f = λf the Helmholtz equation ∂g ∆g = ∂t the heat equation ∂ 2g ∆g = ∂t2 the wave equation Above, x, y, z are the standard coordinates on a suitable domain U in R3 , t is the time variable, f = f (x, y, z) and g = g(x, y, z, t). In addition, the function f (resp., g) is required to satisfy suitable boundary conditions (resp., initial conditions) on the boundary of U (resp., for t = 0). act v. agir action action bound borne bounded borné(e) bounded above borné(e) supérieurement bounded below borné(e) inférieurement unbounded non borné(e) comma virgule concave function fonction concave condition condition boundary condition condition au bord initial condition condition initiale constant n. constante constant adj. constant(e) constant function fonction constant(e) non-constant adj. non constant(e) 21  non-constant function fonction non constante continuous continu(e) continuous function fonction continue convex function fonction convexe decrease n. diminution decrease v. décroı̂tre decreasing function fonction décroissante strictly decreasing function fonction strictement décroissante derivative dérivée second derivative dérivée seconde n-th derivative dérivée n-ième partial derivative dérivée partielle differential n. différentielle differential form forme différentielle differentiable function fonction dérivable twice differentiable function fonction deux fois dérivable n-times continuously differentiable function fonction n fois continument dérivable domain domaine equation équation the heat equation l’équation de la chaleur the wave equation l’équation des ondes function fonction graph graphe increase n. croissance increase v. croı̂tre increasing function fonction croissante strictly increasing function fonction strictement croissante integral intégrale interval intervalle closed interval intervalle fermé open interval intervalle ouvert half-open interval intervalle demi ouvert Jacobian matrix matrice jacobienne Jacobian le jacobien [= le déterminant de la matrice jacobienne] linear linéaire non-linear non linéaire maximum maximum global maximum maximum global local maximum maximum local minimum minimum global minimum minimum global local minimum minimum local monotone function fonction monotone strictly monotone function fonction strictement monotone 22 operator opérateur the Laplace operator opérateur de Laplace ordinary ordinaire order ordre otherwise autrement partial partiel(le) PDE [= partial differential equation] EDP sign signe value valeur complex-valued function fonction à valeurs complexes real-valued function fonction à valeurs réelles variable variable complex variable variable complexe real variable variable réelle function in three variables fonction en trois variables with respect to [= w.r.t.] par rapport à This is all Greek to me Small Greek letters used in mathematics α alpha β beta γ gamma δ delta , ε epsilon ζ zeta η eta θ, ϑ theta ι iota κ kappa λ lambda µ mu ν nu ξ xi o omicron π, $ pi ρ, % rho σ sigma τ tau υ upsilon φ, ϕ phi χ chi ψ psi ω omega Capital Greek letters used in mathematics B Beta Γ Gamma ∆ Delta Θ Theta Λ Lambda Ξ Xi Π Pi Σ Sigma Υ Upsilon Φ Phi Ψ Psi Ω Omega 23  Sequences, Series Convergence criteria P∞ By definition, an infinite series of complex numbers n=1 an converges (to a complex number s) if the sequence of partial sums sn = a1 + · · · + an has a finite limit (equal to s); otherwise it diverges. The simplest convergence criteria are based on the following two facts. P∞ P∞ Fact P∞ 1. If n=1 |an | is convergent, so is n=1 an (in this case we say that the series n=1 an is absolutely convergent). P∞ Fact P∞ 2. If 0 ≤ an ≤ b n for all sufficiently large n and if n=1 bn converges, so does n=1 an. P∞ Taking bn = rn and using the fact that the geometric series n=1 rn of ratio r is convergent iff |r| < 1, we deduce from Fact 2 the following statements. The ratio test (d’Alembert). P∞ If there exists 0 < r < 1 such that, for all sufficiently large n, |an+1 | ≤ r |an |, then n=1 an is (absolutely) convergent. The root test (Cauchy). p P∞ If there exists 0 < r < 1 such that, for all sufficiently large n, n |an | ≤ r, then n=1 an is (absolutely) convergent. What is the sum 1 + 2 + 3 + · · · equal to? At first glance, the answer is easy and not particularly interesting: as the partial sums 1, 1 + 2 = 3, 1 + 2 + 3 = 6, 1 + 2 + 3 + 4 = 10,... tend towards plus infinity, we have 1 + 2 + 3 + · · · = +∞. It turns out that something much more interesting is going on behind the scenes. In fact, there are several ways of “regularising” this divergent series and they all lead to the following surprising answer: 1 (the regularised value of) 1 + 2 + 3 + · · · = −. 12 How is this possible? Let us pretend that the infinite sums a = 1 + 2 + 3 + 4 + ··· b = 1 − 2 + 3 − 4 + ··· c = 1 − 1 + 1 − 1 + ··· all make sense. What can we say about their values? Firstly, adding c to itself yields 24   c = 1 − 1 + 1 − 1 + ···   1 c= 1 − 1 + 1 − ··· =⇒ c =.  2 c + c = 1 + 0 + 0 + 0 + ··· = 1  Secondly, computing c2 = c(1 − 1 + 1 − 1 + · · ·) = c − c + c − c + · · · by adding the infinitely many rows in the following table c = 1 − 1 + 1 − 1 + ··· −c = − 1 + 1 − 1 + · · · c= 1 − 1 + ··· −c = − 1 + ···...... we obtain b = c2 = 41. Alternatively, adding b to itself gives  b = 1 − 2 + 3 − 4 + ···   c 1 b= 1 − 2 + 3 − ··· =⇒ b = =.  2 4 b + b = 1 − 1 + 1 − 1 + ··· = c  Finally, we can relate a to b, by adding up the following two rows: ) a = 1 + 2 + 3 + 4 + ··· 1 1 =⇒ −3a = b = =⇒ a = −. −4a = − 4 − 8 − ··· 4 12 Exercise. Using the same method, “compute” the sum 12 + 22 + 32 + 42 + · · ·. lim f (x) = 2 the limit of f of x as x tends to one is equal to two x→1 approach approcher close proche arbitrarily close to arbitrairement proche de compare comparer comparison comparaison converge converger convergence convergence criterion (pl. criteria) critère diverge diverger 25 divergence divergence infinite infini(e) infinity l’infini minus infinity moins l’infini plus infinity plus l’infini large grand large enough assez grand sufficiently large suffisamment grand limit limite tend to a√limit admettre √ une limite tends to 2 tends vers 2 neighbo(u)rhood voisinage sequence suite bounded sequence suite bornée convergent sequence suite convergente divergent sequence suite divergente unbounded sequence suite non bornée series série absolutely convergent series série absolument convergente geometric series série géométrique sum somme partial sum somme partielle 26  Prime Numbers An integer n > 1 is a prime (number) if it cannot be written as a product of two integers a, b > 1. If, on the contrary, n = ab for integers a, b > 1, we say that n is a composite number. The list of primes begins as follows: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61... Note the presence of several “twin primes” (pairs of primes of the form p, p + 2) in this sequence: 11, 13 17, 19 29, 31 41, 43 59, 61 Two fundamental properties of primes – with proofs – were already contained in Euclid’s Elements: Proposition 1. There are infinitely many primes. Proposition 2. Every integer n ≥ 1 can be written in a unique way (up to reordering of the factors) as a product of primes. Recall the proof of Proposition 1: given any finite set of primes p1 ,... , pj , we must show that there is a prime p different from each pi. Set M = p1 · · · pj ; the integer N = M + 1 ≥ 2 is divisible by at least one prime p (namely, the smallest divisor of N greater than 1). If p was equal to pi for some i = 1,... , j, then it would divide both N and M = pi (M/pi ), hence also N − M = 1, which is impossible. This contradiction implies that p 6= p1 ,... , pj , concluding the proof. The beauty of this argument lies in the fact that we do not need to know in advance any single prime, since the proof works even for j = 0: in this case N = 2 (as the empty product M is equal to 1, by definition) and p = 2. It is easy to adapt this proof in order to show that there are infinitely many primes of the form 4n + 3 (resp., 6n + 5). It is slightly more difficult, but still elementary, to do the same for the primes of the form 4n + 1 (resp., 6n + 1). Questions About Prime Numbers Q1. Given a large integer n (say, with several hundred decimal digits), is it possible to decide whether or not n is a prime? Yes, there are algorithms for “primality testing” which are reasonably fast both in theory (the Agrawal-Kayal-Saxena test) and in practice (the Miller-Rabin test). Q2. Is it possible to find concrete large primes? Searching for huge prime numbers usually involves numbers of special form, such as the Mersenne numbers Mn = 2n − 1 (if Mn is a prime, n is necessarily also a prime). The point is that there is a simple test (the Lucas-Lehmer criterion) for deciding whether Mn is a prime or not. 27  In practice, if we wish to generate a prime with several hundred decimal digits, it is computationally feasible to pick a number randomly and then apply a primality testing algorithm to numbers in its vicinity (having first eliminated those which are divisible by small primes). Q3. Given a large integer n, is it possible to make explicit the factorisation of n into a product of primes? [For example, 999 999 = 33 · 7 · 11 · 13 · 37.] At present, no (unless n has special form). It is an open question whether a fast “prime factorisation” algorithm exists (such an algorithm is known for a hypothetical quantum computer). Q4. Are there infinitely many primes of special form? According to Dirichlet’s theorem on primes in arithmetic progressions, there are infinitely many primes of the form an + b, for fixed integers a, b ≥ 1 without a common factor. It is unknown whether there are infinitely many primes of the form n2 + 1 (or, more generally, of the form f (n), where f (n) is a polynomial of degree deg(f ) > 1). Similarly, it is unknown whether there are infinitely many primes of the form 2n − 1 (the Mersenne primes) or 2n + 1 (the Fermat primes). Q5. Is there anything interesting about primes that one can actually prove? Green and Tao have recently shown that there are arbitrarily long arithmetic progressions consisting entirely of primes. digit chiffre prime number nombre premier twin primes nombres premiers jumeaux progression progression arithmetic progression progression arithmétique geometric progression progression géométrique 28  Probability and Randomness Probability theory attempts to describe in quantitative terms various random events. For example, if we roll a die, we expect each of the six possible outcomes to occur with the same probability, namely 16 (this should be true for a fair die; professional gamblers would prefer to use loaded dice, instead). The following basic rules are easy to remember. Assume that an event A (resp., B) occurs with probability p (resp., q). Rule 1. If A and B are independent, then the probability of both A and B occurring is equal to pq. For example, if we roll the die twice in a row, the probability that we get twice 6 points is equal to 61 · 16 = 36 1. Rule 2. If A and B are mutually exclusive (= they can never occur together), then the probability that A or B occurs is equal to p + q. For example, if we roll the die once, the probability that we get 5 or 6 points is equal 1 to 6 + 16 = 31. It turns out that human intuition is not very good at estimating probabilities. Here are three classical examples. Example 1. The winner of a regular TV show can win a car hidden behind one of three doors. The winner makes a preliminary choice of one of the doors (the “first door”). The show moderator then opens one of the remaining two doors behind which there is no car (the “second door”). Should the winner open the initially chosen first door, or the remaining “third door”? Example 2. The probability that two randomly chosen people have birthday on the same 1 day of the year is equal to 365 (we disregard the occasional existence of February 29). Given n ≥ 2 randomly chosen people, what is the probability Pn that at least two of them have birthday on the same day of the year? What is the smallest value of n for which Pn > 12 ? Example 3. 100 letters should have been put into 100 addressed envelopes, but the letters got mixed up and were put into the envelopes completely randomly. What is the probability that no (resp., exactly one) letter is in the correct envelope? See the next page for answers. coin pièce (de monnaie) heads face toss [= flip] a coin lancer une pièce probability probabilité die (pl. dice) dé random aléatoire fair [= unbiased] die dé non pipé randomly chosen choisi(e) par hasard biased [= loaded] die dé pipé tails pile roll [= throw] a die lancer un dé with respect to [= w.r.t.] par rapport à 29 Answer to Example 1. The third door. The probability that the car is behind the first (resp., the second) door is equal to 13 (resp., zero); the probability that it is behind the third one is, therefore, equal to 1 − 13 − 0 = 32. Answer to Example 2. Say, we have n people with respective birthdays on the days D1 ,... , Dn. We compute 1 − Pn , namely, the probability that all the days Di are distinct. There are 365 possibilities for each Di. Given D1 , only 364 possible values of D2 are distinct from D1. Given distinct D1 , D2 , only 363 possible values of D3 are distinct from D1 , D2. Similarly, given distinct D1 ,... , Dn−1 , only 365 − (n − 1) values of Dn are distinct from D1 ,... , Dn−1. As a result, 364 363 365 − (n − 1) 1 − Pn = · ··· ,  365 365  365   1 2 n−1 Pn = 1 − 1 − 1− ··· 1 −. 365 365 365 One computes that P22 = 0.476... and P23 = 0.507.... In other words, it is more likely than not that a group of 23 randomly chosen people will contain two people who share the same birthday! Answer to Example 3. Assume that there are N letters and N envelopes (with N ≥ 10). The probability pm that there will be exactly m letters in the correct envelopes is equal to   1 1 1 1 1 1 pm = − + − + ··· ± m! 0! 1! 2! 3! (N − m)! (where m! = 1 · 2 · · · m and 0! = 1, as usual). For small values of m (with respect to N ), pm is very close to the infinite sum 1m −1   1 1 1 1 1 1 qm = − + − + ··· = = e , m! 0! 1! 2! 3! e · m! m! which is the probability occurring in the Poisson distribution, and which does not depend on the (large) number of envelopes. In particular, both p0 and p1 are very close to q0 = q1 = 1e = 0.368..., which implies that the probability that there will be at most one letter in the correct envelope is greater than 73% ! depend on dépendre de (to be) independent of (d’être) indépendant de correspondence correspondance transcendental transcendant 30