### 数学代写|离散数学作业代写discrete mathematics代考|Roth’s Theorem

statistics-lab™ 为您的留学生涯保驾护航 在代写离散数学discrete mathematics方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写离散数学discrete mathematics代写方面经验极为丰富，各种代写离散数学discrete mathematics相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

## 数学代写|离散数学作业代写discrete mathematics代考|Roth’s Theorem

Notation. In this subsection, $i$ is reserved for $i=\sqrt{-1}$ and for $c \in \mathbb{C}$ we use $\bar{c}$ to represent the complex conjugate.

We will be doing analysis over the group $\left(\mathbb{Z}{n,}+\right):$ for $f: \mathbb{Z}{n} \rightarrow \mathbb{C}$, let the (discrete) Fourier transform of $f$ be denoted by $\hat{f}$ and given by (for $t \in \mathbb{Z}{n}$ ): $$\widehat{f}(t)=\frac{1}{n} \sum{k=0}^{n-1} f(k) \overline{\chi(k t)}$$

Instead of appealing to van der Waerden’s Theorem as was done in the proof of Theorem 2.67, our goal is now to prove arithmetic progressions exist in certain sets. We start with the simplest case to consider: 3 -term arithmetic progressions. This does not mean that the result concerning these is easy to prove. In 1952 , Roth $[174]$ proved that any subset of $\mathbb{Z}^{+}$with positive upper density must contain a 3 -term arithmetic progression. Note that since every finite coloring of $\mathbb{Z}+$ must have at least one color with positive upper density, Roth’s Theorem is stronger than the existence of $w(3 ; r)$ for all $r \in \mathbb{Z}^{+}$.

Theorem $2.68$ (Roth’s Theorem). For any $\epsilon>0$, there exists $N=N(\epsilon)$ such that for any $n \geq N$, if $A \subseteq[1, n]$ with $|A|>\epsilon n$, then $A$ contains a S-term arithmetic progression.
Remark. Another way of stating Roth’s Theorem is: $r_{3}(n)=o(n)$.
Since we are dealing with 3 -term arithmetic progressions, we can consider integer solutions to $x+y=2 z$, where $x, y$, and $z$ are not all equal. To effectively use discrete Fourier analysis, instead of looking for solutions in $\mathbb{Z}^{+}$, we will be looking at solutions in $\mathbb{Z}_{n}$, so we are considering solutions to $x+y \equiv 2 z$ $\left(\bmod n\right.$ ). A simple observation will allow us to translate back to $\mathbb{Z}^{+}$.

The general approach of the proof is to consider cases depending on the sizes of the Fourier transform coefficients. It is best to have a little intuition into what these mean. Consider the recovery formula given in part (i) of Theorem 1.9:
\begin{aligned} f(j) &=\sum_{k=0}^{n-1} \widehat{f}(k) \chi(k j) \ &=\sum_{k=0}^{n-1} \widehat{f}(k) e^{\frac{2 \pi i k j}{n}} \ &=\sum_{k=0}^{n-1} \widehat{f}(k) \cos \left(\frac{2 \pi k j}{n}\right)+i \sum_{k=0}^{n-1} \widehat{f}(k) \sin \left(\frac{2 \pi k j}{n}\right) \ &=\widehat{f}(0)+\sum_{k=1}^{n-1} \widehat{f}(k) \cos \left(\frac{2 \pi k j}{n}\right)+i \sum_{k=1}^{n-1} \widehat{f}(k) \sin \left(\frac{2 \pi k j}{n}\right) \cdot(2.9) \end{aligned}
The first observation is that $\widehat{f}(0)$ is a constant term in $f(j)$, while the other values of $\hat{f}(k)$ are contracted by a factor depending on $j$. To guide our intuition, we then couple this with the fact that any periodic function over $\mathbb{R}$ (like $\cos (x)$ ) has roots in arithmetic progression (not necessarily of integers).
First, we need to recall how we translate from a set $A \subseteq[1, n]$ to a function $f: \mathbb{Z}_{n} \rightarrow \mathbb{C}$ by using the indicator function:
$$A(j)= \begin{cases}1 & \text { if } j \in A \ 0 & \text { if } j \notin A\end{cases}$$

## 数学代写|离散数学作业代写discrete mathematics代考|Szemerédi’s Theorem

Translating the proof of Roth’s Theorem to address longer arithmetic progressions presents the challenge of moving from solving the equation $x+y=2 z$ to solving a system of equations. Clearly, more sophisticated Fourier analysis tools are needed and this was done twenty years later by Roth $[175]$ for 4 -term arithmetic progressions. However, this was after Szemerédi [195] proved the result via combinatorial methods. Szemerédi then went on to prove his famous theorem for arbitrarily long arithmetic progressions in [196]:

Theorem 2.70 (Szemerédi’s Theorem). For any $k \in \mathbb{Z}^{+}$and any subset $A \subseteq \mathbb{Z}^{+}$, if limsup $\operatorname{sun}_{n \rightarrow \infty} \frac{|A \cap[1, n]|}{n}>0$, then A contains a $k$-term arithmetic progression. Equivalently, given $\epsilon>0$ there exists an integer $N(k, \epsilon)$ such that for all $n>N(k, \epsilon)$, if $|A|>\epsilon n$, then $A$ contains a $k$-term arithmetic progression.

Szemerédi’s proof has been referred to as elementary. This does not mean easy. It is better referred to as “from first principles,” as Szemerédi felt just the logic of the proof warranted a flow chart. This chart is a directed graph on 24 vertices with 36 edges.

The reader is encouraged to work through this combinatorial feat. In this book, we prove Szemerédi’s Theorem in Section 5.2.1, relying on results that we will not prove.

It is worth noting here that Szemerédi’s Theorem is equivalent, by Theorem $2.67$, to the following theorem, the proof of the equivalence being left to the reader as Exercise $2.23$. Note also that Theorem $2.70$ settles the value of $L$ in Theorem 2.67.

Theorem 2.71. For all $k \in \mathbb{Z}^{+}$, there exists a minimal integer $N(k)$ such that for every partition of ${1,2, \ldots, n}=A \sqcup B$ with $|A| \geq|B|$ and $n \geq N(k)$, the set $A$ contains a $k$-term arithmetic progression.

It is interesting to notice that van der Waerden’s Theorem can be very similarly stated as: For all $k \in \mathbb{Z}^{+}$, there exists a minimal integer $M(k)$ such that for every partition of ${1,2, \ldots, m}=A \sqcup B$ with $m \geq M(k)$, one of $A$ and $B$ contains a $k$-term arithmetic progression.

In this section, we will investigate a closely related result that, on the surface, seems as if it may be sufficient to prove Szemerédi’s Theorem. One possible thought about sets satisfying the condition in Theorem $2.70$ is that they cannot have arbitrarily long gaps (forewarning: this is not true) or, if they do, then there must be arbitrarily long intervals where they don’t (forewarning: this is not true either). These seem reasonable, so we will investigate what we can say about this situation.

Definition $2.72$ (Syndetic, Piecewise syndetic). Let $S=\left{s_{i}\right}_{i \in Z^{+}}$. We say that $S$ is syndetic if there exists $d \in \mathbb{Z}^{+}$such that $\left|s_{i+1}-s_{i}\right| \leq d$ for all $i \in \mathbb{Z}^{+}$. We say that $S$ is piecewise syndetic if there exists $d \in \mathbb{Z}^{+}$such that for any $n \in \mathbb{Z}^{+}$, there exists $j \in \mathbb{Z}^{+}$such that $\left|s_{i+1}-s_{i}\right| \leq d$ for $i=j, j+1, \ldots, j+n-1$.

## 数学代写|离散数学作业代写discrete mathematics代考|Density Hales-Jewett Theorem

We start with the statement of the theorem in this subsection’s title:
Theorem 2.74 (Density Hales-Jewett Theorem). Let $\epsilon>0$ and let $k, r \in$ $\mathbb{Z}^{+}$. Let $\mathcal{W}(m)$ be the set of all variable words of length $m$ over the alphabet ${1,2, \ldots, k} \cup{x}$. There exists an integer $N=N(\epsilon, k)$ such that for any $n \geq N$, every subset $S \subseteq[1, k]^{n}$ with $|S|>\epsilon k^{n}$ admits $w(x) \in \mathcal{W}(n)$ with ${w(i): i \in[1, k]} \subseteq S .$

This result was originally proved by Furstenberg and Katznelson [77] using ergodic theory (see Section $5.2$ for an introduction to ergodic theory techniques). Over 30 years later a combinatorial proof was developed [160]. Needless to say, both proofs are very deep and are not appropriate for this

book. For a good exposition of Theorem 2.74, visit the last chapter of [161] (written by Steger; see the Foreword of [161]).

We remark that the $k=2$ case follows by viewing $x_{1} x_{2} \cdots x_{n} \in[1,2]^{n}$ as the subset of $[1, n]$ containing $i$ if and only if $x_{i}=2$. Consider the lattice of $[1,2]^{n}$ partially ordered by inclusion of the associated subsets, i.e., an edge connects two subsets if one is a subset of the other. We are searching for $w(x) \in \mathcal{W}(n)$ such that $w(1)$ and $w(2)$ are both in $S$. This means that we are looking for two subsets connected by an edge.

Recall the concept of an antichain in a poset. An antichain is a set of elements in the lattice with no edge between any of them. A fundamental poset result is Sperner’s Lemma, which states that every antichain of the subsets of $[1, n]$ under inclusion partial ordering has size at most
$$\left(\begin{array}{c} n \ \left\lfloor\frac{n}{2}\right\rfloor \end{array}\right)=\frac{n !}{\left\lfloor\frac{n}{2}\right\rfloor^{2}} \approx \frac{\sqrt{2 \pi n}\left(\frac{n}{e}\right)^{n}}{\pi n\left(\frac{n / 2}{e}\right)^{n}}=\frac{2^{n}}{\sqrt{\frac{\pi}{2} n}}=o\left(2^{n}\right)$$
where we are using Stirling’s approximation. Lastly, note that if our set $S$ has $|S| \geq \epsilon \cdot 2^{n}$, then $S$ cannot be an antichain since it contains more than $o\left(2^{n}\right)$ elements. Hence, $S$ must contain two elements with an edge between them, which is what we want to show.

## 数学代写|离散数学作业代写discrete mathematics代考|Roth’s Theorem

F(j)=∑ķ=0n−1F^(ķ)χ(ķj) =∑ķ=0n−1F^(ķ)和2圆周率一世ķjn =∑ķ=0n−1F^(ķ)因⁡(2圆周率ķjn)+一世∑ķ=0n−1F^(ķ)罪⁡(2圆周率ķjn) =F^(0)+∑ķ=1n−1F^(ķ)因⁡(2圆周率ķjn)+一世∑ķ=1n−1F^(ķ)罪⁡(2圆周率ķjn)⋅(2.9)

## 数学代写|离散数学作业代写discrete mathematics代考|Szemerédi’s Theorem

Szemerédi 的证明被称为基本证明。这并不意味着容易。最好将其称为“从第一原则”，因为 Szemerédi 认为证明的逻辑需要流程图。该图是一个有 24 个顶点和 36 条边的有向图。

## 数学代写|离散数学作业代写discrete mathematics代考|Density Hales-Jewett Theorem

(n ⌊n2⌋)=n!⌊n2⌋2≈2圆周率n(n和)n圆周率n(n/2和)n=2n圆周率2n=这(2n)

## 有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

## MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。