Two topics in arithmetic combinatorics

Roy, Souktik

Permalink

https://hdl.handle.net/2142/120122 Copy

Description

Title

Two topics in arithmetic combinatorics

Author(s)

Roy, Souktik

Issue Date

2023-04-28

Director of Research (if dissertation) or Advisor (if thesis)

Balogh, Jozsef

Doctoral Committee Chair(s)

Kostochka, Alexandr

Committee Member(s)

• Ford, Kevin
• Bradshaw, Peter

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• sum product
• o-minimality
• Sidon sets

Abstract

This thesis - naturally delineated into two parts - attempts to address two flavors of problems in arithmetic combinatorics. These two parts are based on the papers \cite{JRT} and \cite{BFR}, respectively - all mathematical content in this thesis has already appeared in these papers (and associated preprints). In the first, together with Jing and Tran \cite{JRT} we find inspiration in the sum-product phenomenon and the classification of two-variable polynomials of bounded growth. For a bivariate $P(x,y) \in \RR[x,y]\setminus (\RR[x] \cup \RR[y])$, our first result shows that for all finite $A \subseteq \RR$, $|P(A,A)|\geq \alpha|A|^{5/4}$ with $\alpha =\alpha(\deg P) \in \RR^{>0}$ unless $$ P(x,y)=f(\gamma u(x)+\delta u(y)) \text{ or } P(x,y)=f(u^m(x)u^n(y)) $$ for some univariate $f, u \in \RR[t]\setminus \RR$, constants $\gamma, \delta \in \RR^{\neq 0}$, and $m, n\in \NN^{\geq 1}$. This resolves the symmetric nonexpanders classification problem proposed by de Zeeuw. Our second and third results in this chapter are sum-product type theorems for two polynomials, generalizing the classical result by Erd\H os and Szemer\'edi as well as a theorem by Shen. We also obtain similar results for $\CC$, and from this deduce results for fields of characteristic $0$ and fields of large prime characteristic. We use tools from semialgebraic/o-minimal geometry to prove these results; exposition is provided on these methods to make them accessible to readers primarily concerned with combinatorics. In the second, together with Balogh and F\"uredi \cite{BFR}, we combine two elementary proofs to show that the maximum size of a Sidon set of $\{ 1, 2, \ldots, n\}$ is at most $\sqrt{n}+ 0.998n^{1/4}$ for sufficiently large $n$ - the first non-constant improvement of the error term $n^{1/4}$ in this classical combinatorial number theory problem since 1969. This implies improvements in some related problems which are also discussed.

Graduation Semester

2023-05

Type of Resource

Thesis

Handle URL

https://hdl.handle.net/2142/120122

Copyright and License Information

Copyright 2023 Souktik Roy

Owning Collections