The polynomial method and its applications  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
120154
Type K
Principal investigator Károlyi, Gyula
Title in Hungarian A polinom módszer és alkalmazásai
Title in English The polynomial method and its applications
Keywords in Hungarian kombinatorikus nullhelytétel, véges testek
Keywords in English Combinatorial Nullstellensatz, Finite Fields, Gröbner basis
Discipline
Mathematics (Council of Physical Sciences)100 %
Ortelius classification: Discrete mathematics
Panel Mathematics and Computing Science
Department or equivalent Department of Algebra and Number Theory (Eötvös Loránd University)
Participants Kós, Géza
Nagy, Zoltán Lóránt
Nagy, Zoltán Lóránt
Sziklai, Péter
Starting date 2016-10-01
Closing date 2022-06-30
Funding (in million HUF) 12.648
FTE (full time equivalent) 10.66
state closed project
Summary in Hungarian
A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.
A polinom módszer gyökerei Rédei László munkásságáig nyúlnak vissza, melynek új lendületet adott Noga Alon 1999-es cikke, melyben Hilbert nullhelytételének egy effektív változatát bizonyítja Descartes-szorzatokra, számos alkalmazással. A kombinatorikus nullhelytétel az elimináció-elméletben kulcsszerepet játszó Gröbner-bázisok segítségével is megfogalmazható. Az ezáltal kibontakozó elméletnek rengeteg következménye van, elsősorban a kombinatorikus számelmélet, a véges geometria és az extremális kombinatorika, gráfelmélet területén, de a statisztikus mechanika kvantum többtest problémáját megközelítő Calogero-Sutherland-Moser modell
belső szabadsági fokokat is megengedő változatának közelebbi megértésében is szerepet játszik.

Mindezen fejlemények eléréséhez a pályázat résztvevői egyenként és együttes munka keretében is lényegesen hozzájárultak.
A jelen pályázat ezen munkák összehangolt folytatását célozza meg az algebrai módszer kiterjesztésével és további alkalmazások feltérképezésével.

Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.
Az egyik vizsgálandó kérdés magának a polinom módszernek a kiterjesztése. Noha nem várható, hogy Hilbert nullhelytétele teljes általánosságban alkalmazható legyen céljainkra, úgy véljük, hogy Descartes-szorzatoknál kevésbé merev varietásokra is érvényes lehet a kombinatorikus nullhelytételhez hasonló effektív változat, ilyennek igénye már több probléma vizsgálata esetén felmerült. Ezen túlmenően fontosnak tartjuk az algebrai eszköztár bővitését, többek között tenzor-, illetve külső szorzat terek lineáris transzformációinak minimálpolinomjától Lie algebrai technikákon keresztül az algebrai csoportok elméletének bevetéséig. Ez utóbbira már többen is felhívták figyelmünket (Gisbert Wüstholz, Eva Bayer).

Konkrét alkalmazások tekintetében többek között a következőket tervezzük. Kombinatorikus számelméletben a megszorított összegzésre vonatkozó Erdős-Heilbronn problémához kapcsolódó strukturális eredmények, Freiman 3k-4 tételének pontos moduláris
megfelelője, Snevily problémájához kapcsolódó kérdések és annak nemkommutatív csoportokra történő általánosítása. Véges geometriában az irányprobléma vizsgálata. Kombinatorikában Ramsey-típusú kérdések, keresési problémák, illetve az Erdős-Faber-Lovász sejtés vizsgálata. Analízisben újabb Selberg-típusú integrálformulák, ezzel párhuzamosan algebrai kombinatorikában újabb konstans-tag azonosságok megtalálása.

Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!
A kombinatorikus nullhelytétel következményeként adódó nemeltűnési feltétel (polinom-lemma) viszonylag egyszerűen alkalmazható,
noha időnként a releváns együttható meghatározása igen nehéz és körülményes. Az elmúlt másfél évtizedben rengeteg eredmény született e téren. Az együttható formulára vonatkozó munkánk számos korábbi eredmény bizonyítását (Alon, Bressoud, Kadell, Lladó. Morris, Nathanson, Ruzsa, Selberg, Sun, Zeilberger) lényegesen leegyszerűsítette és utat nyitott 20 éve megoldatlan kérdések tisztázására (Forrester, Kadell) is. Ezen a téren számos további előrelépésben reménykedünk. Több munkánk igazolja, hogy magának a kombinatorikus nullhelytételnek közvetlen alkalmazása, mely általában igen nehéz, finom vizsgálatokat igényel, mély struktúrális eredmények elérésére ad lehetőséget. Csapatunk ezen a téren is úttörőnek mondható.

Közvetlen társadalmi hasznosítás nem várható, azonban módszereink, eredményeink egy részét szeretnénk a magasabb szintű hazai felsőoktatásban meghonosítani, emelve ezzel annak minőségét, nemzetközi elismertségét.

A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média, illetve az érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal számára.
A kutatás fő célja algebrai módszerek fejlesztése és alkalmazása a matematika számos területén (analízis, geometria, kombinatorika,
számelmélet). A megcélzott eredmények hasznosak lehetnek a számítástudomány és a statisztikus fizika területén is. Közvetlen társadalmi hasznosítás nem várható, azonban módszereink, eredményeink egy részét szeretnénk a magasabb szintű hazai felsőoktatásban meghonosítani, emelve ezzel annak minőségét, nemzetközi elismertségét.
Summary
Summary of the research and its aims for experts
Describe the major aims of the research for experts.
The polynomial method has its roots in the work of László Rédei. It got a new momentum after the 1999 seminal paper of Noga Alon, where he proved an effective version of Hilbert's Nullstellensatz for Cartesian products along with various applications. The so-called Combinatorial Nullstellensatz can be interpreted also in the context of Gröbner bases, which play a key role in elimination theory.
It leads to a method with many applications, mainly in the areas of combinatorial arithmetic, finite geometry and extremal combinatorics, graph theory. It is also instrumental in the better understanding of the Calogero-Sutherland-Moser model for
quantum manybody systems in statistical mechanics, in particular when internal degrees of freedom are allowed.

The participants of the present proposal have contributed significant results to these developments, both individually and in collaboration. Our goal is an orchestrated continuation of this work, including the extension of the algebraic method and the exploration of its further applications.

What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.
One problem to study is the extension of the polynomial method. Although Hilbert's Nullstellensatz in its full generality cannot be expected to be applicable to our purposes, we believe that an effective version similar to the Combinatorial Nullstellensatz may be valid for varieties with less rigid structure than Cartesian products. The need for such variants has already emerged in several cases.
Moreover we find it important to extend the algebraic toolkit, from the minimal polynomial of linear transformations of tensor and exterior product spaces to Lie algebra techniques to the theory of algebraic groups. The latter possibility was drawn to our attention by Eva Bayer and Gisbert Wüstholz.

As to particular applications, among others we plan the following. In combinatorial number theory, obtaining structural results for restricted set addition related to the Erdős-Heilbronn problem, an exact modular counterpart of Freiman's 3k-4 theorem, relatives of Snevily's problem and its generalization to noncommutative groups. In finite geometry, the study of the direction problem. In combinatorics, the investigation of Ramsey-type problems, search problems, and the Erdős-Faber-Lovász conjecture. In analysis to find new Selberg-type integral formulas along with the corresponding constant term identities in algebraic combinatorics.

What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.
The non-vanishing criterion obtained as a consequence of the Combinatorial Nullstellensatz ( Polyomial Lemma) is relatively easy to apply, although the computation of the relevant coefficient sometimes is rather difficult and involved. During the last 15 years a
tons of results were obtained this way. Our recent research involving the Coefficient Formula led to relatively simple proofs of former results (Alon, Bressoud, Kadell, Lladó, Morris, Nathanson, Ruzsa, Selberg, Sun, Zeilberger) and culminated in solving 20-years-old open problems (Forrester, Kadell). We count on further developments in this area. It is justified by our previous work that the direct application of the Combinatorial Nullstellensatz, which usually requires rather difficult and fine investigations, can lead to deep structural results. Our reserach group is playing a pioneering role in this respect.

Although we do not expect a direct social impact, it is our intention to incorporate some of our methods and results into advanced courses of our higher education, increasing its quality and international reputation.

Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NRDI Office in order to inform decision-makers, media, and others.
The main objective of the proposal is the development of algebraic methods and their appilcation in various fields of mathematics (analysis, combinatorics, geometry, number theory). Our expected results may find applications in computer science and statistical physics as well. It is not realistic to expect a direct social impact; however it is our intention to incorporate our methods and results
in advanced courses of our higher education, increasing its quality and international reputation.




 

Final report

  
Results in Hungarian
A kombinatorikus nullhelytétel segítségével megoldottuk Erdős, Faber és Lovász bizonyos gráfok színezési számára vonatkozó régi sejtésének speciális eseteit. Snevily kommutatív csoportok összeadási táblájának négyzetes részmátrixaiban található latin transzverzálisokra vonatkozó sejtésének a megoldását a prímrendű esetben kiterjesztettük multihalmazokra. A kombinatorikus nullhelytétel és hézagos polinomok segítségével struktúrális stabilitási eredményt bizonyítottunk rácsok hipersíkokkal való fedéseire nézve. A Rédei-polinomok segítségével értünk el eredményeket a cilinder sejtés egy enyhített változazában. Véges nilpotens gyűrűk fölött gyors polinomiális algoritmust adtunk polinomok értékkészletének meghatározására, ami magában foglalja az egyenlet-megoldhatósági problémát. Aszimptotikusan meghatároztuk véges testek fölötti minimális kódok minimáls hosszát. Egy gráfokra vonatkozó szuperszaturációs problémára megjavítotuk Erdős és Simonovits korábbi eredményeit. Véges affin síkokon vizsgáltunk olyan ponthalmazokat, melyek majdnem regulárisan viselkednek párhuzamos egyenesek ostályaira nézve. A kivételes egyenesek viselkedését polinomok és algebrai görbék segítségével visgáltuk. Véges geometriai struktúrákra alapozva tanulmányoztunk titokmegosztási sémákat. Alon részhalmaz-összegekben előforduló számtani sorozatokra vonatkozó régi sejtését egy jóval erősebb formában bizonyítottuk, belátva továbbá Lev egy rokon sejtését is.
Results in English
Based on the Combinatorial Nullstelensatz we solved special cases of a long-standing conjecture of Erdős, Faber and Lovász related to the chromatic number of certain graphs. In the prime order case we extended the solution of a conjecture of Snevily asking for the existence of a Latin transversal in the square submatrices in the addition table of commutative groups of odd order, here elements may appear with multiplicities. We proved structural stability results concerning hyperplane covers of grids with the help of the Combinatorial Nullstellensatz and lacunary polynomials. We proved results for a relaxed version of the cylinder conjecture with the help of the Rédei-polynomials. We gave a fast polynomial algorithm to determine the value set of polynomials over finite nilpotent rings, which include the equation solvability problem. We determined the minimal length of minimal codes over finite fields up to a small constant factor. We improved earlier results of Erdős and Simonovits for a graph supersaturation problem. We investigated point sets in finite affine planes, almost regular in a sense with respect to some parallel classes of lines. The behavior of the exceptional lines are studied using polynomials and algebraic curves over finite fields. We investigated secret sharing schemes based on finite geometric structures. We proved a lot stronger version of an old conjecture of Alon related to arithmetic progressions in subset sums and proved a related conjecture of Lev.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=120154
Decision
Yes





 

List of publications

  
Károlyi, Gy, Szabó, Cs: Evaluation of polynomials in finite rings via additive combinatorics, Bull London Math Soc (Q1), submitted, 2017
Harcos, G, Károlyi, Gy: Selberg's identity for Kloosterman sums, Preprint, 2017
Blázsik, ZL, Nagy, ZL: Partition dimension of projecive planes, European J. Combin (Q1). 65: 37-44, 2017
Nagy, ZL: Saturating sets in projeczive planes and hypergraph covers, Discrete Math (Q1), submitted, 2017
Barát J, Nagy ZL: Transversals in generalized Latin squares, Ars Math Contemp (Q1), submitted, 2017
Nagy, ZL: Coupon-coloring and total domination in Hamiltonian planar triangulations, Graphs and Combinatorics (Q2), submitted, 2017
Nagy, ZL: Saturating sets in projeczive planes and hypergraph covers, Discrete Math (Q1), 341: 1078-1083, 2018
Barát J, Nagy ZL: Transversals in generalized Latin squares, Ars Math Contemp (Q1), 16: 39-47, 2019
Nagy, ZL: Coupon-coloring and total domination in Hamiltonian planar triangulations, Graphs and Combinatorics (Q2), accepted, 2018
Nagy ZL: Supersaturation of C4: from Zarankiewicz towards Erdős-Simonovits-Sidorenko, European J Combin (Q1), 75: 19-31, 2019
Blokhuis A, Nagy ZL: A short note on a novel, Vandermonde-type representation of finite projective planes, Preprint, 2018
De Beule J, Demeyer J, Mattheus S, Sziklai P: On the cylinder conjecture, Designs, Codes and Cryptography, accepted, 2018
Károlyi Gy: An atypical extremal problem for set systems with a constraint on pairwise unions, Preprint, 2018
Károly Gy: Long arithmetic progressions in subset sums and a conjecture of Alon, Preprint, 2018
Jayasuriya SM, Károlyi Gy, Reich SD, Wheeler JP: On critical pairs for restricted set addition in non-nilpotent groups, Preprint, 2018
Károlyi Gy, Szabó Cs: Evaluation of polynomials in finite rings via additive combinatorics, Pub Mat (Q1), submitted, 2019
Harcos G, Károlyi Gy: Selberg's identity for Kloosterman sums, Preprint, 2017
Blázsik Z, Nagy ZL: Partition dimension of projecive planes, European J. Combin (Q1). 65: 37-44, 2017
Nagy ZL: Saturating sets in projeczive planes and hypergraph covers, Discrete Math (Q1), 341: 1078-1083, 2018
Nagy ZL: Coupon-coloring and total domination in Hamiltonian planar triangulations, Graphs and Combinatorics (Q2), accepted, 2018
De Beule J, Demeyer J, Mattheus S, Sziklai P: On the cylinder conjecture, Designs, Codes and Cryptography (Q2), 87:879-893, 2019
Károlyi Gy: Long arithmetic progressions in subset sums and a conjecture of Alon, Preprint, 2018
Hermann Gy, Sziklai P: On a Ramsey-type theorem for lattices, Discrete Math (Q1), submitted, 2019
Ligeti P, Sziklai P, Takáts M: Generalized threshold secret sharing and finite geometry, Preprint, 2019
Nagy ZL, Blázsik Z: Spreading linear triple systems and expander triple systems, Acta Math Univ Comenianae, 88:977-984, 2019
Damásdi G, Martínez-Sandoval L, Nagy DT, NagyZL: Triangle areas determined by arrangements of planar lines, Preprint, 2019
Grzesik A, Janzer O, Nagy ZL: Turán number of blow-ups of trees, Preprint, 2019
Károlyi Gy, Szabó Cs: Evaluation of polynomials in finite rings via additive combinatorics, Pub Mat (Q1), accepted, 2020
Nagy ZL: Saturating sets in projective planes and hypergraph covers, Discrete Math (Q1), 341: 1078-1083, 2018
Nagy ZL: Coupon-coloring and total domination in Hamiltonian planar triangulations, Graphs and Combinatorics (Q2), 34: 1385-1394, 2018
De Beule J, Demeyer J, Mattheus S, Sziklai P: On the cylinder conjecture, Designs, Codes and Cryptography (Q2), 87: 879-893, 2019
Ligeti P, Sziklai P, Takáts M: Generalized threshold secret sharing and finite geometry, Des Codes Cryptography (Q2), submitted, 2020
Blázsik Z, Nagy ZL: Spreading linear triple systems and expander triple systems, European J Combin (Q1), 89:103155 (16 pages), 2020
Damásdi G, Martínez-Sandoval L, Nagy DT, Nagy ZL: Triangle areas in line arrangements, Discrete Math (Q1), 343:112105 (11 pages), 2020
Grzesik A, Janzer O, Nagy ZL: Turán number of blow-ups of trees, J Combin Th B (Q1), submitted, 2019
Gáspár A, Kós G: A Snevily-type inequality for multisets, Acta Math Hungar (Q2), accepted, 2020
Blázsik Z, Blokhuis A, Miklavic S, Nagy ZL, Szőnyi T: On the balanced upper chromatic number of finite projective planes, Discrete Math (Q1), accepted, 2020
Janzer O, Methuku A, Nagy ZL: On the Turán number of the blow-up of the hexagon, Preprint, 2020
Janzer O, Nagy ZL: Coloring linear hypergraphs: the Erdős-Faber-Lovász conjecture and the Combinatorial Nullstellensatz, Des Codes Cryptography (Q2), submitted, 2020
Gerbner D, Nagy ZL, Vizer M: Unified approach to the generalized Turán problem and supersaturation, Discrete Applied Math (Q2), submitted, 2020
Csajbók B, Sziklai P, Weiner Zs: Renitent lines, European J Combin (Q1), submitted, 2020
Károlyi Gy, Szabó Cs: Evaluation of polynomials in finite rings via additive combinatorics, Pub Mat (Q1), 66:197-205, 2022
Ligeti P, Sziklai P, Takáts M: Generalized threshold secret sharing and finite geometry, Des Codes Cryptography (Q2), 89:2067-2078, 2021
Harrach N, Sziklai P, Storme L,Takáts M: Resultant methods inhigher dimensions, preprint, 2021
Matolcsi D, Nagy ZL: Generalized outerplanar Turán numbers and maximum numbers of k-regular subtrees, Discr Appl Math 307:115-124, 2021
Nagy ZL, Szemerédi L: Steiner triple systems and spreading sets in projectice spaces, Preprint, 2021
Héger T, Nagy ZL: Short minimal codes and covering codes via strong blocking sets in projectice spaces, IEEE Transactions on Information Theory (Q1), accepted, 2021
Barnkopf P, Nagy ZL, Paulovics A: A note on internal partitions: the 5-regular case and beyond, Preprint, 2021
Sziklai P, Weiner Zs: Covering all but the low weight vertices of the hypercube, J Combin Theory A (Q1), 193:105671 (6 pages), 2023
Grzesik A, Janzer O, Nagy ZL: Turán number of blow-ups of trees, J Combin Th B (Q1), 156:299-309, 2022
Gáspár A, Kós G: A Snevily-type inequality for multisets, Acta Math Hungar (Q2), 164:46-50, 2021
Blázsik Z, Blokhuis A, Miklavic S, Nagy ZL, Szőnyi T: On the balanced upper chromatic number of finite projective planes, Discrete Math (Q1), 344:112266, 2021
Janzer O, Methuku A, Nagy ZL: On the Turán number of the blow-up of the hexagon, SIAM J Discrete Math (Q1), 36(2), 2022
Janzer O, Nagy ZL: Coloring linear hypergraphs: the Erdős-Faber-Lovász conjecture and the Combinatorial Nullstellensatz, Des Codes Cryptography (Q2), 90:1991-2001, 2022
Gerbner D, Nagy ZL, Vizer M: Unified approach to the generalized Turán problem and supersaturation, Discrete Applied Math (Q2), 345(3):112743, 2022
Harrach N, Sziklai P, Storme L,Takáts M: Resultant methods in higher dimensions, preprint, 2021
Matolcsi D, Nagy ZL: Generalized outerplanar Turán numbers and maximum numbers of k-regular subtrees, Discr Appl Math (Q2) 307:115-124, 2022
Nagy ZL, Szemerédi L: Steiner triple systems and spreading sets in projectice spaces, J Combin Designs (Q2), 30:549-560, 2022
Héger T, Nagy ZL: Short minimal codes and covering codes via strong blocking sets in projectice spaces, IEEE Transactions on Information Theory (Q1), 68:881-890, 2021
Barnkopf P, Nagy ZL, Paulovics A: A note on internal partitions: the 5-regular case and beyond, Graphs amd Combinatorics, submitted, 2021
Károlyi Gy: Long arithmetic progressions in subset sums and a conjecture of Alon, J Number Theory (Q1), submitted, 2022
Borbély J, Károlyi Gy: Covering Cartesian products by hyperplanes, manuscript, 2022



Back »