Matrices dont deux lignes quelconque coïncident dans un nombre donne de positions communes

Le nombre maximal de lignes de matrices seront désignées par:

1. (a) R(k, λ) si chaque ligne est une permutation de nombres 1, 2,…, k et si chaque deux lignes différentes coïncide selon λ positions;

2. (b) S⁰(k, λ) si le nombre de colonnes est k et si chaque deux lignes différentes coïncide selon λ positions et si, en plus, il existe une colonne avec les éléments y₁, y₂, y₃, ou y₁ = y₂ ≠ y₃;

3. (c) T⁰(k, λ) si c'est une (0, 1)-matrice et si chaque ligne contient k unités et si chaque deux lignes différentes contient les unités selon λ positions et si, en plus, il existe une colonne avec les éléments 1, 1, 0.

La fonction T⁰(k, λ) était introduite par Chvátal et dans les articles de Deza, Mullin, van Lint, Vanstone, on montrait que T⁰(k, λ) max(λ + 2, (k − λ)² + k − λ + 1). La fonction S⁰(k, λ) est introduite ici et dans le Théorème 1 elle est étudiée analogiquement; dans les remarques 4, 5, 6, 7 on donne les généralisations de problèmes concernant T⁰(k, λ), S⁰(k, λ), dans la remarque 9 on généralise le problème concernant R(k, λ). La fonction R(k, λ) était introduite et étudiée par Bolton. Ci-après, on montre que R(k, λ) S⁰(k, λ) T⁰(k, λ) d'où découle en particulier: R(k, λ) λ + 2 pour λ k + 1 − (k + 2)^1/2; R(k, λ) = 0(k²) pour k − λ = 0(k); R(k, λ) (k − 1)² − (k + 2) pour k 1191.     

On Extremal Permutations AvoidingωN = NN − 1 . . . 1

Dedicated to the memory of Marcel–Paul Schützenberger Cet article présente une étude des permutations qui évitent le motif de la permutation maximaleω_N = NN − 1 . . . 1. Après avoir donné les définitions classiques, nous montrons que l’ensemble de ces permutations est un idéal pour l’ordre de Bruhat faible et faisons l’étude de ses éléments maximaux. Nous exhibons alors un algorithme pour calculer ces éléments et nous montrons que ceux-ci peuvent être obtenus à partir d’un automate. Nous terminons en donnant des estimations asymptotiques de leur nombre. This paper presents a study of permutations avoiding the patternω_N = NN − 1 . . . 1. After recalling the basic definitions, we prove that this set of permutations is an ideal for the weak Bruhat order and begin the study of its maximal elements. We then present an algorithm that generates these elements and find out that they can be obtained from an automaton. Finally, we give some asymptotics about their number.     

Critères d'induction et de coinduction pour certains anneaux d'opérateurs différentiels

Soit une algèbre de Lie opérant par dérivations sur un anneau local commutatif noethérien (R, ,K=R/ ), et soit V l'anneau des opérateurs différentiels construits à partir de R et . Posons ( )={d /d( ) } et ₀ = ( )/ : ₀ est une algèbre de Lie qui opère sur K par dérivations et l'on peut construire un anneau d'opérateurs différentiels sur K à l'aide de ₀, noté V₀. Grâce au (V₀ − V)-bimodule V/ V on définit l'induction (resp. la coinduction) de V₀ à V par Ind^V_v0=−_v0V/ V (resp. Coind^V_v0=Hom_v0(V/ V,−)) et on donne un critère pour qu'un V-module soit induit (resp. coinduit) à partir de V₀. Ces résultats sont des analogues de ceux, établis par Mackey pour les groupes de Lie et par Blattner pour les algèbres de Lie, analogues, basés sur la notion de système d'imprimitivité.Let be a Lie algebra acting by derivations on a commutative noetherian local ring (R, ,K=R/ ) and let V be the ring of differential operators built on R and . Defining ( )={d /d( ) } et ₀ = ( )/ : ₀ is a Lie algebra which acts on K by derivations, and we can construct a differential operators ring on K with ₀, denoted by V₀. With the help of the (V₀ − V)-bimodule V/ V we define the induction (resp. coinduction) from V₀ to V by Ind^V_v0=−_v0V/ V and we give a criterion for a V-module to be induced (resp. coinduced) from V₀. These results are similar to those established by Mackey for Lie groups and Blattner for Lie algebras, which are based on the notion of the system of imprimitivity.     

Opérateurs elliptiques sur les variétés non compactes

Soient M une variété, V un ouvert de M, et P un opérateur différentiel elliptique du second ordre, à coefficients C^∞ et réels tel que P1 0. Soit A_V l'opérateur induit par P dans l'espace de Banach C₀(V) des fonctions continues sur V nulles au point à l'infini de V, muni de la norme du suprémum. On démontre que A_V engendre un semi-groupe fortement continu à contraction ssi il existe K compact de V, h fonction continue strictement positive dans VβK et nulle au point à l'infini de V telle que (1 − P) h soit la distribution associée à une fonction continue non négative dans VβK. On en déduit immédiatement un résultat bien connu: si M est une variété de Cartan-Hadamard, A_M engendre un semi-groupe fortement continu à contraction dans C₀(M).Let M be a manifold, V an open set of M, and P an elliptic differential operator of the second order, with real C^∞ coefficients and such that P1 0. Let A_V be the operator induced by P in the complex Banach space C₀(V) of all continuous functions vanishing at the point at infinity of V, endowed with the supremum norm. One proves that A_V generates a strongly continuous contraction semi-group iff there exists K compact of V, h continuous strictly positive in VβK and 0 at infinity of V such that (1 − P) h is the distribution associated to a nonnegative continuous function in VβK. One deduces immediately from that a well-known result: if M is a Cartan-Hadamard manifold, A_M generates a strongly continuous contraction semigroup in C₀(M).     

Noyaux potentiels associés à une filtration

We study from the point of view of potential theory some operators V which are “integrals of martingales” and noteworthy the formula (I + V)⁻¹ = I − N where N is a submarkovian kernel. We give an explicit expression of N when the filtration is finite and get the general case with an usual approximation procedure. Some links are made with the matrix theory (ultrametric and Stieltjes matrices) and the graph theory (flows and capacities) when the space is finite.

Résumé

On étudie, du point de vue de la théorie du potentiel, des opérateurs V du type “intégrales de martingale”, et notamment la formule (I + V)⁻¹ = I − N où N est un noyau sous-markovien. On donne une expression explicite de N dans le cas d'une filtration finie, et on traite le cas général par un procédé d'approximation usuel. On fait le lien avec la théorie des matrices (matrices ultramétriques et de Stieltjes) et la théorie des graphes (flots et capacités) quand l'espace est fini.     

The N-dimensional matching polynomial

Heilmann et Lieb ont introduit le polynôme de couplage μ(G, x) d’un graphe G = (V, E). Nous prolongeons leur définition en munissant chaque sommet de G d’une forme linéaire N-dimensionnelle (ou bien d’un vecteur) et chaque arête d’une forme symétrique bilinéaire. On attache donc à tout r-couplage de G le produit des formes linéaires des sommets qui ne sont pas saturés par le couplage, multiplié par le produit des poids des r arêtes du couplage, où le poids d’une arête est la valeur de sa forme évaluée sur les deux vecteurs de ses extrémités. En multipliant par (−1)^r et en sommant sur tous les couplages, nous obtenons notre polynôme de couplage N-dimensionnel. Si N = 1, le théorème principal de l’article de Heilmann et Lieb affirme que tous les zéros de μ(G, x) sont réels. Si N = 2, cependant, nous avons trouvé des graphes exceptionnels où il n’y a aucun zéro réel, même si chaque arête est munie du produit scalaire canonique. Toutefois, la théorie de la dualité développée dans [La1] reste valable en N dimensions. Elle donne notamment une nouvelle interprétation à la transformation de Bargmann–Segal, aux diagrammes de Feynman et aux produits de Wick.Heilmann and Lieb have introduced the matching polynomial μ(G, x) of a graph G = (V, E). We extend their definition by associating to every vertex of G an N-dimensional linear form (or a vector) and to every edge a symmetric bilinear form. For every r-matching of G we define its weight as the product of the linear forms of the vertices not covered by the matching, multiplied by the product of the weights of the r edges of the matching, where the weight of an edge is the value of its form evaluated at the two vectors of its end points. Multiplying by (−1)^r and summing over all matchings, we get our N-dimensional matching polynomial. If N = 1, the Heilmann–Lieb theorem affirms that all zeroes of μ(G, x) are real. If N = 2, however, there are exceptional graphs without any real zero at all, even if the canonical scalar product is associated to every edge. Nevertheless, the duality theory developed in [La1] remains valid in N dimensions. In particular, it brings new light to the Bargmann–Segal transform, to the Feynman diagrams, and to the Wick products.Received: February 2004 Revision: July 2004 Accepted: August 2004     

Front Propagation Problems with Nonlocal Terms, II

We study the propagation of hyper surfaces Σ_t of ^N satisfying the equation V = h(x, Ω_t), where V is the normal velocity of Σ_t at x, Ω_t is the interior of Σ_t, and h is a given evolution law. We prove the existence of generalized solutions and an inclusion principle for these generalized solutions. Copyright 2001 Academic Press.Dans cet article nous étudions certains problèmes de propagation d'hypersurfaces Σ_t de ^N suivant des lois de la forme: V = h(x, Ω_t), où V est la vitesse normale à Σ_t en x, Ω_t est l'intérieur de Σ_t et h est une loi d'évolution. On définit une notion de solutions généralisées, et on montre l'existence de telles solutions. De plus on démontre un principe d'inclusion pour ces solutions.     

Critical path analysis for continuum percolation

We prove the validity of the Critical path analysis for a continuum percolation model close to Golden–Kozlov one. This is obtained in the limit of strong disorder.

Résumé

On montre la validité de “Critical path analysis” pour un modèle de percolation continue proche de celui de Golden–Kozlov. Le résultat est obtenu à la limite de grand désordre.     

Leibniz et le problème des partis. Quelques papiers inédits

Depuis son voyage à Paris, en 1672, Leibniz se montre intéressé à l'aspect mathématique de la théorie de la probabilité. En automme 1672, il fait la connaissance de Huygens, qui va l'initier en Mathématiques, rencontre Malebranche et Arnauld, et peut examiner, en 1673, quelques-uns des manuscrits de Pascal. De retour à Hanovre, il essaye de faire ses propres calculs. Sont connus déià les manuscrits “Sur le calcul des partis” du 5 janvier 1676 et “De incerti æstimatione,” de septembre 1678, commentés entre autres par K.-R. Biermann. Ici on va commenter un nouveau manuscrit, de 1686, qui résout le fameux problème de Bernoulli sur le sort de deux joueurs et qui est resté inédit jusqu'ici.     

Le rapport di isou (Euclide V, définition 17): Définition, utilisation, transmission

Dans le livre V des Eléments d'Euclide, la définition 17, du di isou logos, se compose de deux énoncés juxtaposés, qui ne sont pas équivalents. Le premier étant une simple réfection du théorème V,22, il convient de regarder le second seul comme authentique, comme le suggérent aussi bien l'emploi de l'expression di isou en géométrie grecque, que l'analyse précise de la tradition indirecte. En conséquence, la définition 17 doit être débarrassée de sa première partie; la définition 18.1, celle de la proportion réglée, doit être restituée comme authentique; la définition 18.2, de la proportion déréglée, doit être réduite à son libellé original, analogue à celui de 18.1.In Euclid's Elements V, Definition 17 (di isou logos) consists of two statements, which are not equivalent. The first one being a remake of theorem V,22, the second is the only one to be taken as genuine. This can be proved by the use of the expression di isou in Greek geometry, and also by a close scrutiny of the various witnesses of this part of the text. Consequently, Definition 17 should be cleared of its first part; Definition 18.1, of the ordered proportion, should be restored as genuine; Definition 18.2, of the perturbed proportion, should be reduced to its original core, and made similar to 18.1.     

Problèmes linéaires dans le Compendy de la praticque des nombres de Barthélemy de Romans et Mathieu Préhoude (1471): Une approche nouvelle basée sur des sources proches du Liber abbaci de Léonard de Pise

The Compendy de la praticque des nombres (1471) is one of a number of commercial arithmetics produced in southern France during the medieval period. Its interest and originality rest in its treatment of problem-solving. The author of the text limited his treatment to an in-depth analysis of only a few types of problems, not treating particular cases but rather emphasizing general methods. The sources from which he drew were very close to the Liber abbaci of Leonardo Fibonacci and many of them were new to the southern French arithmetic tradition. Thus, the Compendy sheds new light on the transmission of arithmetic thought into Europe. Copyright 2000 Academic Press.Le Compendy de la praticque des nombres (1471) est un traité qui appartient au groupe des arithmétiques commerciales du Sud de la France. L'intérêt et l'originalité du texte résident dans la partie consacrée à la résolution de problèmes. L'auteur sélectionne quelques types de problèmes seulement, auxquels il consacre une longue étude, délaissant les cas particuliers pour privilégier les méthodes. Ce faisant, il utilise de nouvelles sources, proches du “Liber abbaci” de Léonard de Pise, étrangères aux autres arithmétiques françaises de la même famille. Le Compendy nous apporte ainsi un éclairage nouveau sur la transmission de l'algorisme. Copyright 2000 Academic Press.MSC subject classifications: 01A35; 01A40.     

Comparaison des deux composantes d''un subordinateur bivarié, puis étude de l''enveloppe supérieure d''un processus de Lévy

Soit (Y,Z) un subordinateur bivarié. Nous donnons une condition suffisante pour que Y_t/Z_t converge vers zéro quand t tend vers 0 ou +∞. Ceci généralise partiellement des résultats de Bertoin et de Kesten–Erickson.Soit X un processus de Lévy et S_t=sup{X_s: st}. Soit f une fonction sous-additive. En appliquant le résultat précédent au subordinateur bivarié d'échelle, nous donnons des conditions nécéssaires et suffisantes pour que et égalent 0 ou +∞.Let (Y,Z) be a bivariate subordinator. Generalizing theorems of Bertoin and Kesten–Erickson, we give a sufficient condition for Y_t/Z_t to converge to 0 when t tends either to 0 or +∞.Let X be a Lévy process. Denote by S_t=sup{X_s: st} and let f be any sub-additive function. Applying our first result to the bivariate ladder process, we give necessary and sufficient conditions for and to be either 0 or +∞.     

Coboundaries in

Let T be an ergodic automorphism of a probability space, f a bounded measurable function, . It is shown that the property that the probabilities μ(|S_n(f)|>n) are of order n^−p roughly corresponds to the existence of an approximation in L^∞ of f by functions (coboundaries) g−g○T, gL^p. Similarly, the probabilities μ(|S_n(f)|>n) are exponentially small iff f can be approximated by coboundaries g−g○T where g have finite exponential moments.

Résumé

Soit T un automorphisme ergodique d'un espace probabilisé, f une fonction bornée mesurable et . Une correspondance est établie entre l'existence de l'estimation des probabilités μ(|S_n(f)|>n) d'ordre n^−p et l'existence de l'approximation dans L^∞ de la fonction f par des cobords g−g○T où g est “presque” dans L^p. De manière similaire, les probabilités μ(|S_n(f)|>n) sont d'ordre e^−cn, pour un certain c>0, n=1,2… , si et seulement si f admet une approximation dans L^∞ par des cobords g−g○T avec g ayant des moments exponentiels.     

Constantes d’Erdös–Turán

L’inégalité d’Erdös-Turán mesure l’écart à l’équirépartition d’une suite quelconque du tore en fonction d’un paramètre arbitraire et de deux constantes absolues, c₁ et c₂. Nous montrons que c₁≥ 1 et c₂≥ 2/π, et nous fournissons un ensemble de couples admissibles (c₁;c₂) numériquement proches de l’optimum hypothétique (1;2/π), notamment (1;0,653) et (1,1435;2/π).The Erdös-Turán inequality measures the distance from uniform distribution of any given sequence on the torus as a function of an arbitrary parameter and two constants, c₁ and c₂. We show that c₁≥ 1 and c₂≥ 2/π, and we provide a set of admissible pairs (c₁;c₂) that are numerically close to the hypothetical optimum (1;2/π), including (1;0.653) and (1.1435;2/π).À Jean-Louis Nicolas, avec toute notre amitié2000 Mathematics Subject Classification: Primary—11K38, 11K06; Secondary—11L03, 42A05     

Représentation des fonctionnelles surmédianes

Summary Considérons la théorie du potentiel définie par un noyau de Hunt: si F est une fonction complètement additive de certaines mesures et croissante en ordre du balayage, il existe une (classe de) fonction borélienne représentant F; c'est le résultat principal de ce travail, et il se révèle extrêmement commode pour l'étude des fonctions fortement surmédianes.On en déduit un théorème de convergence du type de Cartan-Brelot pour les familles monotones de fonctions fortement surmédianes, et un critère de compacité relative inspiré de celui de Dunford-Pettis. On précise les termes de la décomposition de Mertens à l'aide du cône C des fonctions fortement surmédianes quasi-s.c.s. modérées.Comme application, on introduit et on étudie la «quasi-topologie fine» et les ensembles réguliers.Toute cette étude repose presque uniquement sur deux propriétés fondamentales, à savoir d'une part le caractère régularisant des opérateurs de réduction, et d'autre part la grande propriété des ensembles semi-polaires qui se trouve originellement chez R.M. Hervé [8] et dont nous donnons ici une version un peu plus forte.Dans un deuxième chapitre, nous signalons les généralisations possibles, et nous obtenons sans affaiblissement les mêmes énoncés en théorie des résolvantes de Ray ou en théorie des surmartingales.     

The Missing Problems of Gersonides—A Critical Edition, II

Gersonides' Maaseh Hoshev (The Art of Calculation) is a major work known for its early use of rigorous combinatorial proofs and mathematical induction. There is a large section of problems at the end of the book, with the theme of proportions, which until now remained unpublished. I present a critical edition of this material. I also uncover a previously unknown second edition of Maaseh Hoshev. The material is appropriate for creative pedagogy and provides economic details of the author's culture and environs. A previous article presented the first, 15 problems and this article presents the rest. Copyright 2000 Academic Press.Le Maase Hoshev (L'Art du Calcul) de Gersonide est un ouvrage majeur connu pour son usage précoce de preuves combinatoires rigoreuses et de l'induction mathématique. La fin de l'ouvrage comporte une section importante consacrée a une série de trente problèmes sur le thème des proportions qui était restée inédite jusqu'à ce jour et dont je présente pour la première fois une édition critique. Je révèle également l'éxistence d'une séconde édition de Maase Hoshev. Le matériau peut servir de base à des projets de pédagogie créative et offre des détails sur la culture et l'environnement de l'auteur. Cet article fait suite a une première étude qui présentait les quinze premiers problèmes de Maase Hoshev et en présente les quinze autres.     

Square Root Approximations in Old Babylonian Mathematics: YBC 7289 in Context

We consider several aspects of the role and evaluation of the four-sexagesimal-place approximation to on the well-known Old Babylonian tablet YBC 7289. By referring to what is known about OB school texts, we show that this text is most probably a school exercise by a trainee scribe who got the approximation from a coefficient list. These coefficient lists are briefly described, with their use in geometrical problems. We consider other texts involving square roots and derive an algorithm for evaluating them, which complies with all known OB examples, from a simple geometrical construction of the type that seems to underlie many other OB procedures.Copyright 1998 Academic Press.Nous considérons plusieurs aspects du rôle et de l'évaluation de l'approximation à quatre places sexagésimales de sur cette tablette paléo-babylonienne. En nous référant à l'état des connaissances quant aux textes scolaires paléo-babyloniens, nous montrons comment ce texte est très probablement un exercice scolaire exécuté par un apprenti scribe qui a obtenu l'approximation à partir d'une liste de coéfficients. Nous décrivons en bref ces listes de coéfficients, ainsi que leur utilisation dans les problèmes de géométrie. Nous considérons d'autres textes traitant de racines carrées , et pour les évaluer nous dérivons un algorithme qui est en accord avec tous les exemples paléo-babyloniens connus; ceci à partir d'une construction géométrique simple du type qui semble être charactéristique de beaucoup d'autres procédures paléo-babyloniennes.Copyright 1998 Academic Press.MSC 1991 subject classifications: 01A17; 11-03     

A Contextualized Historical Analysis of the Kuhn–Tucker Theorem in Nonlinear Programming: The Impact of World War II

When Kuhn and Tucker proved the Kuhn–Tucker theorem in 1950 they launched the theory of nonlinear programming. However, in a sense this theorem had been proven already: In 1939 by W. Karush in a master's thesis, which was unpublished; in 1948 by F. John in a paper that was at first rejected by the Duke Mathematical Journal; and possibly earlier by Ostrogradsky and Farkas. The questions of whether the Kuhn-Tucker theorem can be seen as a multiple discovery and why the different occurences of the theorem were so differently received by the mathematical communities are discussed on the basis of a contextualized historical analysis of these works. The significance of the contexts both mathematically and socially for these questions is discussed, including the role played by the military in the shape of Office of Naval Research (ONR) and operations research (OR). Copyright 2000 Academic Press.En démontrant, en 1950, le théorème qui porte aujourd'hui leur nom, Kuhn et Tucker ont donné naissance à la théorie de la programmation non-linéaire. Cependant, en un sens, ce théorème avait été démontré auparavant, d'abord par W. Karush en 1939 dans un mémoire de maîtrise inédit, par la suite par F. John en 1948 dans un article qui avait d'abord été rejeté par le Duke Mathematical Journal, et peut-être même plus tôt par Ostrogradsky et aussi par Farkas. Le présent article cherche à élucider deux questions: Peut-on considérer le théorème Kuhn–Tucker comme un exemple de découverte multiple? Et pourquoi le théorème a-t-il été reçu si différemment dans les diverses communautés mathématiques? Notre discussion se base sur une analyse historique contextuelle des différents ouvrages. Nous examinons ici l'importance du contexte, tant du point de vue des mathématiques que du point de vue social, y compris le rôle joué par le secteur militaire dans le cadre de l'Office of Naval Research et de la recherche opérationnelle. Copyright 2000 Academic Press.MSC 1991 subject classification: 01A60; 49-03; 52-03; 90-03; 90C30.