Applications of Combinatorics in Multiplicative Number Theory  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
115978
Type PD
Principal investigator Pach, Péter Pál
Title in Hungarian Kombinatorikus eszközök alkalmazása a multiplikatív számelméletben
Title in English Applications of Combinatorics in Multiplicative Number Theory
Keywords in Hungarian sűrűségi tétel, Ramsey-típusú tétel, egyenletek megoldhatósága, multiplikatív Sidon-sorozatok, rainbow-típusú tételek
Keywords in English density theorem, Ramsey-type theorem, equation solvability, multiplicative Sidon-sequences, rainbow-type theorem
Discipline
Mathematics (Council of Physical Sciences)100 %
Ortelius classification: Number theory
Panel Mathematics and Computing Science
Department or equivalent Department of Computer Science and Information Theory (Budapest University of Technology and Economics)
Starting date 2015-09-01
Closing date 2019-08-31
Funding (in million HUF) 20.037
FTE (full time equivalent) 2.34
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 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).
Summary
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).




 

Final report

  
Results in Hungarian
A legfontosabb elért eredmény a polinom módszer egy új változatának kidolgozása, melynek segítségével megmutattuk, hogy Z_4^n csoport egy 3 hosszú számtani sorozatot nem tartalmazó részhalmazának mérete exponenciálisan kicsi. Ez volt az első ,,exponenciális nyereség'' ilyen típusú problémák esetében. A módszer publikálása óta már számos alkalmazása született, például a cap set probléma és az Erdős-Szemerédi napraforgósejtés megoldása. Egy másik főbb eredmény az x+y=p(z) egyenlet Ramsey-problémájának megoldása az egészek fölött. Továbbá számos eredményt értünk el a multiplikatív Sidon-sorozatok és multiplikatív bázisok területén, mint például a legkisebb multiplikatív bázis méretének meghatározása, Erdős egy kapcsolódó kérdésének megválaszolása, a multiplikatív Sidon-sorozatok leszámlálása, illetve végtelen Sidon-sorozatok lehető legnagyobb aszimptotikus sűrűségének meghatározása.
Results in English
The most important result is developing a new variant of the polynomial method to solve a question in Additive Combinatorics, namely to prove that sets avoiding nontrivial 3-term arithmetic progressions in Z_4^n are exponentially small.  This ``exponential saving'' was the first of a kind for problems of this sort, and till then a large number of applications have been seen including the solutions of the cap set problem and the Erdős-Szemerédi sunflower conjecture. An important achievement is resolving the Ramsey problem of the equation x+y=p(z) over the integers. Finally, we obtained a number of results about multiplicative Sidon sets and multiplicative bases, including determining the smallest possible size of a multiplicative basis, answering a related question of Erdős, enumerating the multiplicative Sidon sets and  studying infinite multiplicative Sidon sets. 
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=115978
Decision
Yes





 

List of publications

  
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



Back »