University of Illinois Urbana-Champaign

Two topics in arithmetic combinatorics

Roy, Souktik

Content Files
ROY-DISSERTATION-2023.pdf

Permalink

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

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

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois