Polynôme d'Ehrhart

En mathématiques, on associe à un polytope entier (c'est-à-dire à un polytope convexe dont les coordonnées des sommets sont entières) son polynôme d'Ehrhart (étudié par Eugène Ehrhart (en) vers 1960), lequel décrit une relation entre le volume du polytope et le nombre des points à coordonnées entières qu'il contient. La théorie de ces polynômes peut être vue comme une généralisation du théorème de Pick en dimensions supérieures.

Définition

L'idée de la construction de Ehrhart est de considérer comme fonction de t le nombre de points entiers intérieurs à un polytope obtenu par homothétie par un facteur t du polytope étudié.

Plus précisément, soit un réseau de l'espace euclidien et un polytope P de dont tous les sommets sont des points du réseau (par exemple , on utilise fréquemment le réseau et des polytopes dont tous les sommets ont des coordonnées entières), engendrant un sous-espace affine de dimension d (d est appelé la dimension de P). Pour tout entier positif t, soit tP le polytope obtenu par dilatation de P par un facteur t, c'est-à-dire le polytope obtenu en multipliant par t les coordonnées de tous les sommets (exprimés dans une base du réseau, et soit le nombre de points du réseau contenus dans le polytope tP. Ehrhart (en) montra en 1962 que L est un polynôme en t de degré d, c'est-à-dire qu'il existe des nombres rationnels tels que pour tout entier t.

Le polynôme d'Ehrhart de l'intérieur d'un polytope convexe P de dimension d vérifie résultat connu sous le nom de réciprocité d'Ehrhart–Macdonald[1].

Exemples

Le dilaté correspondant à d'un carré unité contient points entiers.

Soit P un hypercube unité de dimension d, dont les sommets sont les points dont toutes les coordonnées valent 0 ou 1, autrement dit

La dilatation de P par t est un hypercube de côté t, contenant (t + 1)d points entiers, et donc le polynôme d'Ehrhart de P est L(P,t) = (t + 1)d[2],[3]. On voit aussi qu'aux entiers négatifs, on a comme le prédit la réciprocité d'Ehrhart–Macdonald.

Bien d'autres nombres figurés peuvent s'exprimer à l'aide de polynômes d'Ehrhart. Par exemple, les nombres pyramidaux carrés sont donnés par le polynôme d'Ehrhart d'une pyramide à base carrée de côtés et de hauteur 1 ; le polynôme d'Ehrhart est dans ce cas 1/6(t + 1)(t + 2)(2t + 3)[4].

Quasi-polynômes d'Ehrhart

Soit P un polytope rationnel convexe, c'est-à-dire que avec et (cela revient à dire que P est l'enveloppe convexe d'un ensemble fini de points de ). Posons , le nombre de points entiers contenus dans tP. Dans ce cas, L(P, t) est un quasi-polynôme (en) en t, c'est-à-dire que , où les sont des fonctions périodiques de période entière. La loi de réciprocité d'Ehrhart–Macdonald est encore valable : on a .

Exemple de quasi-polynôme d'Ehrhart

Soit P un quadrilatère de sommets (0,0), (0,2), (1,1) et (3/2, 0). Le nombre de points entiers dans tP est donné par le quasi-polynôme [5].

Interprétation des coefficients

Si P est fermé (c'est-à-dire que les faces de la frontière appartiennent à P), certains coefficients de L(P, t) ont une interprétation simple :

  • le coefficient dominant, , est égal au volume d-dimensionnel de P, divisé par , le covolume du réseau  ;
  • le second coefficient, , peut se calculer en partant des réseaux induits par sur les faces F de P : est obtenu en divisant le (d-1)-volume de chaque face F par , et en faisant la somme de ces nombres pour toutes les faces de P ;
  • le coefficient constant a0 est la caractéristique d'Euler de P ; dans le cas convexe et fermé, on a

Séries d'Ehrhart

La série génératrice des polynômes d'Ehrhart pour un polytope P de dimension d est .

Cette série est une fraction rationnelle ; plus précisément, Ehrhart a démontré qu'il existe des nombres complexes (dépendants de P) tels que

De plus, le théorème de non-négativité de Richard Stanley affirme que sous ces hypothèses, les sont des entiers naturels.

Un autre résultat de Stanley montre que si P iest un polytope contenu dans Q (sur le même réseau, on a pour tout j[6].

Séries d'Ehrhart pour des polytopes rationnels

On peut également définir des séries analogues pour un polytope rationnel P de dimension d. Appelant D ile plus petit entier tel que DP soit un polytope entier (D est appelé le dénominateur de P), on a la formule

où les sont encore des entiers naturels[7],[8].

Bornes pour les coefficients

On peut déterminer des bornes pour les coefficients non dominants de la représentation  : on a par exemple[9] , où est un nombre de Stirling de première espèce ; des bornes inférieures existent également[10]

Notes et références

  1. Ian G. Macdonald, « Polynomials associated with finite cell-complexes », Journal of the London Mathematical Society, vol. 2, no 1,‎ , p. 181–192 (DOI 10.1112/jlms/s2-4.1.181)
  2. De Loera, Rambau et Santos 2010.
  3. Mathar 2010.
  4. Beck et al. 2005.
  5. Matthias Beck et Sinai Robins, Computing the Continuous Discretely, New York, Springer, , 46–47 (MR 2271992)
  6. Richard Stanley, « A monotonicity property of -vectors and -vectors », European Journal of Combinatorics, vol. 14,‎ (DOI 10.1006/eujc.1993.1028)
  7. Richard P. Stanley, « Decompositions of rational convex polytopes », Annals of Discrete Mathematics, vol. 6,‎ , p. 333–342 (ISBN 9780444860484, DOI 10.1016/s0167-5060(08)70717-9)
  8. Matthias Beck et Frank Sottile, « Irrational proofs for three theorems of Stanley », European Journal of Combinatorics, vol. 28, no 1,‎ , p. 403–409 (DOI 10.1016/j.ejc.2005.06.003, arXiv math/0501359, S2CID 7801569)
  9. (en) Ulrich Betke et Peter McMullen, « Lattice points in lattice polytopes », Monatshefte für Mathematik, vol. 99, no 4,‎ , p. 253–265 (ISSN 1436-5081, DOI 10.1007/BF01312545, S2CID 119545615)
  10. Martin Henk et Makoto Tagami, « Lower bounds on the coefficients of Ehrhart polynomials », European Journal of Combinatorics, vol. 30, no 1,‎ , p. 70–83 (ISSN 0195-6698, DOI 10.1016/j.ejc.2008.02.009, arXiv 0710.2665, S2CID 3026293)

Bibliographie

Read other articles:

هذا التصنيف مخصص لجمع مقالات البذور المتعلقة بصفحة موضوع عن منتخب كرة قدم وطني بلغاري. بإمكانك المساعدة في توسيع هذه المقالات وتطويرها. لإضافة مقالة إلى هذا التصنيف، استخدم {{بذرة منتخب كرة قدم وطني بلغاري}} بدلاً من {{بذرة}}. هذا التصنيف لا يظهر في صفحات أعضائه؛ حيث إنه مخصص ...

 

2010 World Wrestling Entertainment pay-per-view event WrestleMania XXVIPromotional poster featuring Shawn Michaels, Triple H, John Cena, The Undertaker, and BatistaPromotionWorld Wrestling EntertainmentBrand(s)RawSmackDownDateMarch 28, 2010CityGlendale, ArizonaVenueUniversity of Phoenix StadiumAttendance72,219[1]Buy rate885,000[2]Tagline(s)Get All Fired UpPay-per-view chronology ← PreviousElimination Chamber Next →Extreme Rules WrestleMania chronology ← Pr...

 

In linguistics, an unaccusative verb is an intransitive verb whose grammatical subject is not a semantic agent. In other words, the subject does not actively initiate, or is not actively responsible for, the action expressed by the verb. An unaccusative verb's subject is semantically similar to the direct object of a transitive verb or to the subject of a verb in the passive voice. Examples in English are the tree fell; the window broke. In those sentences, the action (falling, breaking) can ...

Колишня клініка Солецького, в архітектурі якої використовувалися народні гуцульські та закопанські мотиви, архітектор Олександр Лушпинський Будинок акціонерного товариства «Дністер» у Львові (тепер міська поліклініка № 1, вул. Руська, 20), архітектор Іван Левинський Г

 

En droit français, un objectif de valeur constitutionnelle (ou objectif à valeur constitutionnelle) est un objectif dégagé par le Conseil constitutionnel auquel ce dernier reconnaît une valeur constitutionnelle[1],[2]. Ces objectifs trouvent leurs fondements dans le bloc de constitutionnalité constitué de la constitution elle-même, la déclaration des droits de l'homme et du citoyen, le préambule de la constitution de 1946 ainsi que de la charte de l'environnement de 2004. Histoire L...

 

Eduardo Informações pessoais Nome completo Eduardo Fernandes Amorim Data de nasc. 30 de novembro de 1950 (73 anos) Local de nasc. Montes Claros, Minas Gerais, Brasil Nacionalidade brasileiro Apelido Rabo de Vaca Informações profissionais Posição ex-meio-campista, ex-treinador Clubes profissionais12 Anos Clubes Jogos (golos) 1969–19811981–19871988 CruzeiroCorinthiansSanto André 0556 000(23)0336 000(10)0019 0000(1) Seleção nacional3 1977 Brasil 0001 0000(0) Times/clubes q...

Coupe d'Afrique des nations de football 2004 Généralités Sport Football Organisateur(s) CAF Édition 24e Lieu(x) Tunisie Date du 24 janvier 2004 au 14 février 2004 Participants 16 (49 en phases qualificatives) Épreuves 32 rencontres Affluence 553 500 (moyenne 17 297) Site(s) 6 stades Site web officiel http://fr.cafonline.com/ Palmarès Tenant du titre Cameroun (4) Vainqueur Tunisie (1) Finaliste Maroc Troisième Nigeria Buts 88 (2,75 par match) Cartons jaunes 116 (moyenne 3,63/...

 

Indian reservation in Arizona, United States San Carlos Apache NationTsékʼáádn (Western Apache)Flag of the San Carlos Apache NationLocation of San Carlos Apache Indian ReservationTotal population16,250Regions with significant populationsUnited States (Arizona)LanguagesWestern Apache, Spanish, EnglishReligionTraditional Tribal Religions, Christianity (especially Lutheranism)Related ethnic groupsApache, Navajo(Diné) The San Carlos Apache Indian Reservation (Western Apache: Tsékʼáá...

 

Hashemite Arab FederationUseCivil flag and ensignProportion1:2Adopted14 February 1958Relinquished2 August 1958DesignHorizontal black, white, and green stripes with a red triangle at hoist. The colors are the Pan-Arab Colors. In 1958, in response to the merger of Egypt and Syria in the United Arab Republic, the two Hashemite kingdoms of Iraq and Jordan established the Arab Federation, a confederation of the two states. According to the 7th article of the Federation convention, the Arab revolt ...

ويليام هنري شامبرلن   معلومات شخصية الميلاد 12 فبراير 1870  سولت ليك سيتي  الوفاة سنة 1921[1]  لوغان  مواطنة الولايات المتحدة  إخوة وأخوات رالف فاري تشامبرلين  الحياة العملية المدرسة الأم جامعة شيكاغوجامعة يوتا  المهنة فيلسوف،  وعالم عقيدة  اللغات ا...

 

Brewery located in Chicago, Illinois, US Goose Island Beer CompanyThe Original Goose Island Brewpub on Clybourn Ave. opened in 1988LocationChicago, IllinoisUnited StatesCoordinates41°53′14″N 87°40′20″W / 41.887133°N 87.672134°W / 41.887133; -87.672134Opened1988Key peopleJohn Hall (Founder)Todd Ahsmann (President)Daryl Hoedtke (Brewmaster)Owned byAnheuser-Busch InBevWebsitegooseisland.comActive beers Name Type Goose IPA India Pale Ale 312 Wheat Ale Wheat ale...

 

Legendary musician in Greek mythology For other uses, see Linus (mythology). Linus teaches the letters to Musaeus on the tondo of a kylix. Eretria Painter, circa 440/35 BC. Paris, Louvre. In Greek mythology Linus (Ancient Greek: Λῖνος Linos flax) was a reputed musician and master of eloquent speech.[1] He was regarded as the first leader of lyric song.[2] Family Linus' parentage was given as follows: (1) Muse Calliope and Oeagrus or Apollo,[3] (2) Muse Urania[...

1999 single by Pet Shop Boys I Don't Know What You Want but I Can't Give It Any MoreSingle by Pet Shop Boysfrom the album Nightlife B-side Silver Age Screaming Je t'aime... moi non plus Released19 July 1999 (1999-07-19)StudioQuad (New York City)Length 5:09 (album version) 4:29 (edit) LabelParlophoneSongwriter(s) Neil Tennant Chris Lowe Producer(s) David Morales Pet Shop Boys Pet Shop Boys singles chronology Somewhere (1997) I Don't Know What You Want but I Can't Give It Any Mor...

 

Comic book series Uncanny AvengersCover of Uncanny Avengers #1 (December 2012). Art by John Cassaday & Laura MartinPublication informationPublisherMarvel ComicsScheduleMonthlyFormatOngoing seriesPublication date List (vol. 1) December 2012 – December 2014 (vol. 2)March 2015 – August 2015 (vol. 3) December 2015 – February 2018 No. of issues List (vol. 1): 26 (vol. 2): 5 (vol. 3): 30 Main character(s) List Current members: Doctor VoodooHuman TorchQuicksilverRogue (field leader)Scarlet...

 

FilmShadow of IllusionItalian film poster. Art by Tino Avelli.[1]Directed byMario CaianoScreenplay by Enrico Rossetti Frank Agrama Mario Caiano[1] Story by Enrico Rossetti Frank Agrama Mario Caiano[1] Produced byNino Milano[1]Starring William Berger Daniela Giordano Krista Nell Antonio Cantafora CinematographyEnrico Menczer[1]Edited byTatiana Casini Morigi[1]Music byCarlo Savina[1]ProductioncompanyLiger[1]Distributed byIcarRunnin...

Das Kloster Bronnbach ist das bekannteste und flächenmäßig größte noch erhaltene Kloster im Kreis. Seit 1986 ist das ehemalige Kloster Eigentum des Main-Tauber-Kreises. Die Liste von Klöstern im Main-Tauber-Kreis zeigt ehemalige und noch bestehende Klöster auf dem Gebiet des heutigen Main-Tauber-Kreises in Baden-Württemberg.[1] Die Liste der Klöster ist nach Städten und Gemeinden sowie in der Folge nach Orten sortiert und erhebt keinen Anspruch auf Vollständigkeit. Inhaltsv...

 

1999 studio album by East River PipeThe Gasoline AgeStudio album by East River PipeReleasedAugust 10, 1999Length44:37LabelMerge Records[1]East River Pipe chronology Mel(1996) The Gasoline Age(1999) Garbageheads on Endless Stun(2003) Professional ratingsReview scoresSourceRatingAllMusic[2]Robert Christgau[3]Pitchfork Media8.0/10[4] The Gasoline Age is an album by East River Pipe, released in 1999.[5][6] Critical reception The A.V. Club wr...

 

Lake in Hubei, China Hong LakeHong LakeLocation in HubeiLocationHonghu, HubeiCoordinates29°50′52″N 113°20′26″E / 29.847791°N 113.340454°E / 29.847791; 113.340454Basin countriesChinaSurface area348 km2 (134 sq mi)SettlementsHonghu Hong Lake (Chinese: 洪湖; pinyin: Hóng Hú) is a 348 km2 (134 sq mi) freshwater lake in the municipal region of Jingzhou, in central China's Hubei province. Map including Hong Lake (lab...

Rinzai Zen Buddhist temple in Kyoto Saihō-ji redirects here. For other uses, see Saihō-ji (disambiguation). Saihō-ji西芳寺ReligionAffiliationIndependent Rinzai(formerly Tenryū-ji)DeityAmida Nyorai (Amitābha)LocationLocation56 Matsuo Jingatani-chō, Ukyō-ku, Kyoto, Kyoto PrefectureCountryJapanGeographic coordinates34°59′33″N 135°41′03″E / 34.99250°N 135.68417°E / 34.99250; 135.68417ArchitectureFounderGyōki (acc. legend)(restored by Musō Soseki)Com...

 

Ini adalah nama Melayu; nama Yacob merupakan patronimik, bukan nama keluarga, dan tokoh ini dipanggil menggunakan nama depannya, Halimah. Halimah YacobNama dalam bahasa asli(ms) Halimah Binti Yacob / حاليمه بنت يا(zh) 哈莉玛·雅各布(ta) ஹலிமா பின்தி யாகொப் BiografiKelahiran23 Agustus 1954 (69 tahun)Singapura  8a Presiden Singapura 14 September 2017 – 13 September 2023 ← Tony Tan Keng Yam – Tharman Shanmugara...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!