 |
Kombinatorikus eszközök alkalmazása a multiplikatív számelméletben
|
súgó 
nyomtatás 
|
Ezen az oldalon az NKFI Elektronikus Pályázatkezelő Rendszerében nyilvánosságra hozott projektjeit tekintheti meg.
vissza »
|
| |
Projekt adatai |
|
|
| azonosító |
115978 |
| típus |
PD |
| Vezető kutató |
Pach Péter Pál |
| magyar cím |
Kombinatorikus eszközök alkalmazása a multiplikatív számelméletben |
| Angol cím |
Applications of Combinatorics in Multiplicative Number Theory |
| magyar kulcsszavak |
sűrűségi tétel, Ramsey-típusú tétel, egyenletek megoldhatósága, multiplikatív Sidon-sorozatok, rainbow-típusú tételek |
| angol kulcsszavak |
density theorem, Ramsey-type theorem, equation solvability, multiplicative Sidon-sequences, rainbow-type theorem |
| megadott besorolás |
| Matematika (Műszaki és Természettudományok Kollégiuma) | 100 % | | Ortelius tudományág: Számelmélet |
|
| zsűri |
Matematika–Számítástudomány |
| Kutatóhely |
Számítástudományi és Információelméleti Tanszék (Budapesti Műszaki és Gazdaságtudományi Egyetem) |
| projekt kezdete |
2015-09-01 |
| projekt vége |
2019-08-31 |
| aktuális összeg (MFt) |
20.037 |
| FTE (kutatóév egyenérték) |
2.34 |
| állapot |
lezárult projekt |
magyar összefoglaló 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 kutatás fő célkitűzései:
- Általánosított multiplikatív Sidon-sorozatok elemszámának becslése, vagyis k>2 esetén minél pontosabb választ adni arra a kérdésre, hogy az 1, 2, ..., n számok közül legfeljebb hány választható ki úgy, hogy közülük semelyik 2k különböző ne elégítse ki az a_1a_2...a_k=b_1b_2...b_k egyenletet. Emellett az additív Sidon-sorozatoknál vizsgált kérdésekkel analóg kérdések vizsgálata (pl. másféle értelemben vett sűrűségek). Ezzel a problémakörrel összefüggésben annak az extremális gráfelméleti kérdésnek a vizsgálata, hogy egy 3-reguláris hipergráfnak hány éle lehet, ha nem tartalmaz bizonyos hosszúságú köröket (Berge-féle értelemben).
- Egyenletek (elsősorban a+b=cd, ab+1=cd) Z_m-beli megoldhatóságának vizsgálata összetett m esetén.
- Rainbow-típusú problémák vizsgálata, ezek megoldására alkalmas módszer kidolgozása. Annak a kérdésnek a vizsgálata, hogy mely n-ekre lehetséges a pozitív egészeket n színnel úgy kiszínezni, hogy minden {a, 2a, ..., na} alakú halmaz n-színű ("rainbow") legyen.
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.
G_k(n)-nel jelölve az 1, 2, ..., n számok közül maximálisan kiválasztható olyan elemek számát, amelyek közül semelyek 2k különböző nem elégíti ki az a_1a_2...a_k=b_1b_2...b_k egyenletet, igazolható, hogy G_k(n) aszimptotikusan pi(n), ha n páros, illetve pi(n)+pi(n/2), ha n páratlan. Az egyik célom a fő tag melletti hibatagot minél pontosabban meghatározni k>2 esetén (k=2-re a kérdést Erdős nagyon pontosan megválaszolta).
Emellett más egyenletek megoldhatóságát is vizsgálnám különböző számkörökben.
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!
Az általánosított multiplikatív Sidon-sorozatok elemszámára vonatkozó becslések már önmagukban is érdekesek, viszont míg az additív változatról számtalan eredmény és cikk született, a multiplikatív esetről eddig csak k=2 tényezős szorzatok esetén született ,,pontos'' válasz, melyet Erdős bizonyított. A probléma nehézségét az is mutatja, hogy Erdősnek 31 évvel az első ezzel kapcsolatos eredménye után sikerült megadnia a pontos választ ebben az esetben. A kérdés más kombinatorikus számelméleti kérdésekkel is szorosan összefügg, például: Erdős-Sárközy-T. Sós és Győri vizsgálták azt a kérdést, hogy az 1, 2, ..., n számok közül legfeljebb hányat választhatunk ki, hogy közülük semelyik 2k-nak a szorzata ne legyen négyzetszám.
A különböző számkörökön belül egyenletek megoldhatóságával kapcsolatos Ramsey-típusú és sűrűségi tételek keresése sokat vizsgált kérdés a számelméletben, a célunk olyan esetekre is választ adni, módszert kidolgozni, melyre az eddig kidolgozott módszerek (pl. karakterösszeges becslések mod p) nem használhatók.
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.
Az egyenletek megoldhatósága a matematika több területén belül is sokat vizsgált kérdés. Mi olyan típusú számelméleti problémákra keressük a választ, hogy egy rögzített egyenlet esetén egy bizonyos számkörből legfeljebb hány elemet választhatunk ki úgy, hogy azok közül még ne lehessen kiválasztani úgy néhányat, hogy azok megoldják az egyenletet. Bizonyos esetekben pedig azt vizsgáljuk, hogy a vizsgált számokat néhány színnel kiszínezve garantálható-e, hogy az egyenletnek biztosan legyen olyan megoldása, ahol a benne szereplő változók mind egyforma színűek (ezek a Ramsey-típusú kérdések), illetve páronként különböző színűek (ezek a rainbow-típusú kérdések).
| angol összefoglaló Summary of the research and its aims for experts
Describe the major aims of the research for experts.
The main aims of the research:
- To estimate the size of generalized multiplicative Sidon-sequences, namely, to give an as precise answer as possible to the question that how many numbers can be chosen from 1, 2, ..., n in such a way that no 2k of them would satisfy the equation a_1a_2...a_k=b_1b_2...b_k. Therewidth, to observe questions analogous to questions observed in the case of additive Sidon-sequences, for example, density in different senses. In connection with these problems to observe the extremal graph theoretic question that how many edges a 3-regular hypergraph can have, if it does not contain cycles of certain sizes (in Berge-type sense).
- To investigate the solvability of equations (mainly a+b=cd, ab+1=cd) in Z_m for composite m.
- To examine Rainbow-type problems, to develop method which is suitable to solve them. The investigation of the following problem: For which values of n is it possible to colour the positive integers with n colours in such a way that every set of the form {a, 2a, ..., na} is "rainbow" (its elements have pairwise different colours)?
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.
By denoting by G_k(n) the maximal number of elements which can be chosen from 1, 2, ..., n in such a way that
no 2k distinct elements of them would satisfy the equation a_1a_2...a_k=b_1b_2...b_k, it can be proved that G_k(n) is asymptotically pi(n), if n is even and pi(n)+pi(n/2), if n is odd. One of our aims is to determine the error term as precisely as possible in the case of k>2. (The case k=2 was answered by Erdős very accurately).
Besides I would examine the solvability of other equations.
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 estimates for the size of the generalized multiplicative Sidon-sequences are interesting on their own, but while there are many results about the additive version of the problem, in the multiplicative case only for
k=2 factor products there is a precise answer, which was proved by Erdős. The difficulty of this problem is also shown by the fact that only 31 years after the first result of Erdős in connection with this topic he could give a precise answer in this, k=2, case. This question connects other combinatorial number theoretic quetions as well, for instance, Erdős-Sárközy-T. Sós and Győri examined that how many numbers can be chosen from 1, 2, ..., n in such a way that the product of any 2k of them is not a square number.
To look for Ramsey-type and density theorems in connection with equation solvability in N, Z_m, and so on, is an often investigated question in number theory. Our aim is to give some answers and develop some methods for those cases as well, for which the until known methods (e.g. estimates with character sums mod p) are not applicable.
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 solvability of equations is an often examined question within many areas of the mathematics.
We are looking for answers for the following type number theoretic questions:
Given a certain equation, at most how many elements can be chosen from a certain set in such a way that from them we cannot choose some which would solve the equation? In some cases we would rather observe that by colouring the numbers whether it could be guaranteed that the equation has such solution in which the occuring variables have the same colour (these are the Ramsey-type questions) or have pairwise different colours (these are the rainbow-type questions).
|
|
|
|
|
|
|
|
| |
Közleményjegyzék |
|
|
| Croot E, Lev V F, Pach P P: Progression-free sets in Z_4^n are exponentially small, Ann. of Math., 185 (1) 331-337., 2017 | | Pach P P, Sándor Cs: Multiplicative bases and an Erdős problem, Combinatorica, 38 (5) 1175-1203., 2018 | | Pach P P: Monochromatic solutions to the equation x+y=z^2 in the interval [N,cN^4], Bulletin of the London Mathematical Society, 50 (6) (2018) 1113-1116., 2018 | | Liu H, Pach P P: The number of multiplicative Sidon sets of integers, Journal of Combinatorial Theory, Series A, 165 152-175., 2019 | | Pach P P, Sándor Cs: On infinite multiplicative Sidon sets, European Journal of Combinatorics, 76 (2019) 37-52., 2018 | | Pach P P: An improved upper bound for the size of the multiplicative 3-Sidon sets, Int. J. Number Theory 15 (8) 1721–1729., 2019 | | Hegyvári N, Hennecart F, Pach P P: On the density of sumsets and product sets, Australasian Journal of Combinatorics, 74 (1) (2019) 1-16., 2019 | | Pach P P: Normal forms under Simon’s congruence, Semigroup Forum 97 (2) 251-267., 2018 | | Liu H, Pach P P, Sándor Cs: Polynomial Schur's theorem, (21 pages), submitted, 2019 | | Elsholtz C, Pach P P: Caps and progression-free sets in Z_m^n, (43 pages), submitted, 2019 | | Liu H, Pach P P, Palincza R: The number of maximum primitive sets of integers, (11 pages), submitted, 2019 | | Caicedo A E, Chartier T A C, Pach P P: Coloring the n-smooth numbers with n colors, (60 pages) submitted, 2019 | | Pach P P, Sándor Cs: On infinite multiplicative Sidon sets, submitted, 2017 | | Pach P P: Normal forms under Simon’s congruence, Semigroup Forum 97 (2) 251-267., 2018 | | Pach P P: Monochromatic solutions to the equation x+y=z^2 in the interval [N,cN^4], Bulletin of the London Mathematical Society, to appear, 2018 | | Pach P P: Polynomials, Rank and Cap Sets, Joint International Meeting of the Chinese Mathematical Society and the American Mathematical Society, Shanghai, 2018 | | Pach P P: On multiplicative Sidon sets, Combinatorial and Additive Number Theory, New York, 2018 | | Pach P P: Polynomial Schur's theorem, Arithmetic Ramsey Theory in Manchester, 2018 | | Pach P P, Sándor Cs: On infinite multiplicative Sidon sets, European Journal of Combinatorics, to appear, 2018 | | Pach P P: Polynomials, rank and cap sets, Workshop on Algebraic Methods in Combinatorics, Harvard, 2017 | | Pach P P: Polynomials, rank and cap sets, 10 Year Anniversary DIMAP Workshop, University of Warwick, 2017 | | Pach P P: Normal form for the words under Simon’s congruence, submitted, 2016 | | Pach P P: On some Multiplicative Problems of Erdős, Combinatorial and Additive Number Theory, Graz, 2016 | | Pach P P: On Multiplicative Bases and some Related Problems, Additive Combinatorcs in Bordeaux, 2016 | | Croot E, Lev V F, Pach P P: Progression-free sets in Z_4^n are exponentially small, Ann. of Math., 185 (1) 331-337., 2017 | | Hegyvári N, Hennecart F, Pach P P: On the density of sumsets and product sets, submitted, 2017 | | Pach P P: Progression-free sets and the polynomial method, 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Budapest, 2017 | | Pach P P: Polynomials and progression-free sets, CanaDAM, Toronto, 2017 | | Pach P P: Polynomials and progression-free sets, Journées Arithmétiques, Caen, 2017 | | Pach P P: On progression-free sets via the polynomial method, Vilnius Conference in Combinatorics and Number Theory, Vilnius, 2017 | | Pach P P, Sándor Cs: Multiplicative bases and an Erdős problem, Combinatorica, to appear, 2017 | | Pach P P: Progression-free sets in Z_4^n, Combinatorial and Additive Number Theory, New York, 2016 | | Pach P P: Számtani sorozatot nem tartalmazó halmazok, Matematikai Lapok 22:(1) 1-7., 2016 | | Pach P P: Progression-free sets, Strobl, Conference on Elementary and analytic number theory (ELAZ), 2016 | | Croot E, Lev V F, Pach P P: Progression-free sets in Z_4^n are exponentially small, Ann. of Math., to appear, 2016 | | Pach P P: Normal form for the words under Simon’s congruence, submitted, 2016 | | Pach P P: On some Multiplicative Problems of Erdős, Combinatorial and Additive Number Theory, Graz, 2016 | | Pach P P: On Multiplicative Bases and some Related Problems, Additive Combinatorcs in Bordeaux, 2016 | | Pach P P, Sándor Cs: Multiplicative bases and an Erdős problem, submitted, 2016 | | Pach P P: Generalized multiplicative Sidon sets, Journal of Number Theory 157 507-529., 2015 | | Pach P P: The polynomial method and the cap set problem, One day workshop on Extremal Combinatorics, EWHA University, Seoul, 2019 | | Pach P P: Polynomial Schur's Theorem, London Colloquia in Combinatorics, 2019 | | Pach P P: The polynomial method and the cap set problem, FU Berlin, Colloquium, 2019 | | Pach P P: Polynomials, Rank and Cap Sets, The 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Tokyo, 2019 | | Pach P P: On some applications of graph theory to number theoretic problems, IBS One-Day Conference on Extremal Graph Theory, Daejeon, 2019 | | Pach P P: Polynomials, rank and cap sets, Mathematics Colloquium, TU Graz, 2018 | | Pach P P: Progression-free sets and rank of matrices, Additive combinatorics, Linz, 2018 |
|
|
|
|
|
|
|
|
|
