## Large subsets of discrete hypersurfaces in Z^d contain arbitrarily many collinear points

— 1. Introduction —

Recently, Florian Richter and I uploaded to the arXiv our paper titled Large subsets of discrete hypersurfaces in ${{\mathbb Z}^d}$ contain arbitrarily many collinear points’.

This was the outcome of a fun project which started when we learned about Pomerance’s theorem:

Theorem 1 (Pomerance’s theorem) For every ${B,k\in{\mathbb N}}$ there exists ${n\in{\mathbb N}}$ such that for any ${u_0,\dots,u_n\in{\mathbb Z}^2}$ with average gap bounded by ${B}$, i.e.

$\displaystyle \frac1n\sum_{i=1}^n\|u_i-u_{i-1}\|\leq B,$

there exist ${k}$ points among ${u_1,\dots,u_n}$ which are collinear.

I have presented the proof of Pomerance’s theorem in this post. A weakening of Pomerance’s theorem was proved earlier by L. T. Ramsey (it is Lemma 1 in that paper) as a combinatorial intermediate step in a problem in Fourier analysis.

Lemma 2 (Ramsey’s lemma) For every ${B,k\in{\mathbb N}}$ there exists ${n\in{\mathbb N}}$ such that for any ${u_0,\dots,u_n\in{\mathbb Z}^2}$ with gaps bounded by ${B}$, i.e.

$\displaystyle \forall i\in\{1,\dots,n\}\qquad\qquad\|u_i-u_{i-1}\|\leq B$

there exist ${k}$ points among ${u_1,\dots,u_n}$ which are collinear.

Even when ${B=1}$ Lemma 2 is nontrivial (and in fact it is easy to derive Lemma 2 from the case when ${B=1}$).

The question we asked (and eventually answered) was whether these results could be extended to higher dimensions. The first problem here is how to even formulate such a generalization!

Posted in Analysis, Combinatorics, paper | | 2 Comments

## New polynomial and multidimensional extensions of classical partition results

Vitaly Bergelson, John Johnson and I recently uploaded to the arXiv a paper entitled “New polynomial and multidimensional extensions of classical partition results“. In this post I will give some motivating examples for the results in the paper.

To keep things as concrete as possible, I will establish parallels to our results in the paper using known generalizations of the classical van der Waerden’s theorem on arithmetic progressions:

Theorem 1 (van der Waerden) For any finite partition of the natural numbers ${{\mathbb N}=C_1\cup\cdots\cup C_r}$, there exists some ${i\in[r]=\{1,\dots,r\}}$ for which ${C_i}$ contains arbitrarily long arithmetic progressions, i.e., for every ${k\in{\mathbb N}}$, there are ${a,b\in{\mathbb N}}$ such that

$\displaystyle ja+b\in C_i\qquad\forall j\in[k]\ \ \ \ \ (1)$

Posted in Combinatorics, paper, Ramsey Theory | | 1 Comment

## Weighted densities with multiplicative structure

The upper density of a set ${A\subset{\mathbb N}}$, defined by

$\displaystyle \bar d(A)=\limsup_{N\rightarrow\infty}\frac{\big|A\cap\{1,\dots,N\}\big|}N \ \ \ \ \ (1)$

provides a useful way to measure subsets of ${{\mathbb N}}$. For instance, whenever ${\bar d(A)>0}$, ${A}$ contains arbitrarily long arithmetic progressions, this is Szemerédi’s theorem. A fundamental property of the upper density ${\bar d}$ is that it is invariant under (additive) shifts. More precisely, if we denote by ${A-n}$ the set ${\{x\in{\mathbb N}:x+n\in A\}}$ then ${\bar d(A-1)=\bar d(A)}$ for any ${A\subset{\mathbb N}}$ and ${n\in{\mathbb N}}$.
However the upper density is not invariant under multiplicative shifts’. More precisely, if we let ${A/n:=\{x\in{\mathbb N}:x\cdot n\in A\}}$, then ${\bar d(A/n)}$ is not, in general, the same as ${\bar d(A)}$. For instance, taking ${A}$ to be the set of odd numbers and ${n=2}$ we have ${\bar d(A)=1/2}$ but ${A/n}$ is the empty set, and as such ${\bar d(A/n)=0}$. In fact, as I explored in a previous post, there is very little multiplicative information contained in the upper density ${\bar d}$ of a set. In particular, for any ${\epsilon>0}$, there are sets with upper density ${\bar d(A)>1/2-\epsilon}$ but without any two numbers ${x,y\in A}$ which divide each other; the first examples of such sets were constructed by Besicovitch in 1934. Continue reading

## A proof of Deuber’s theorem using Hales-Jewett’s theorem

In my previous post I explained how Rado’s theorem follows from Deuber’s theorem (which in turn gives a little more than Rado’s theorem, in one direction). The main purpose of this post is to give a full proof of Deuber’s theorem, which will then complete the proof of Rado’s theorem.

I will follow the proof presented in this survey by Gunderson (available here). According to the survey, this proof was first suggested by Leeb and later worked out by Prömel. The main tool for the proof is the Hales-Jewett theorem. I wrote about this theorem twice before in this blog, including a complete proof. In particular I showed how van der Waerden’s theorem on arithmetic progressions, which is an important corollary of Deuber’s theorem, follows from Hales-Jewett’s theorem.

However, Deuber’s theorem (which I will formulate precisely below) implies also Schur’s theorem, and it is not at all clear how to derive Schur’s theorem from Hales-Jewett theorem directly. Thus it is somewhat surprising that one can leverage the Hales-Jewett theorem to deduce Deuber’s theorem. Continue reading

Posted in Combinatorics, Ramsey Theory | Tagged , , | 1 Comment

## Rado’s theorem and Deuber’s theorem

In this post I talk about (and prove) a fundamental theorem of Rado in Ramsey’s theory. I will prove “half” of the theorem and will postpone the second part of the proof to a future post.

To better appreciate Rado’s theorem, I will start by listing some of it’s consequences: {Schur’s theorem}}} For any ${r\in{\mathbb N}}$ and any function ${\chi:{\mathbb N}\rightarrow[r]}$ (as usual we will take ${[r]=\{1,\dots,r\}}$) there exist ${x,y\in{\mathbb N}}$ such that ${\chi(x)=\chi(y)=\chi(x+y)}$.

Equivalently, for any finite coloring of ${{\mathbb N}}$ there exists a monochromatic solution to the equation ${x+y=z}$.

\href{van der Waerden’s theorem}} For any ${r,k\in{\mathbb N}}$ and any function ${\chi:{\mathbb N}\rightarrow[r]}$ there exist ${x,y\in{\mathbb N}}$ such that ${\chi(x)=\chi(x+y)=\cdots=\chi(x+ky)}$.

Equivalently, for any finite coloring of ${{\mathbb N}}$ there exists a monochromatic solution to the system ${x_{i+1}-x_i=x_i-x_{i-1}}$ for ${i=1,\dots,k-1}$.

A common generalization of the two above theorems is Brauer’s theorem:

Theorem 1 (Brauer’s theorem) For any ${r,k\in{\mathbb N}}$ and any function ${\chi:{\mathbb N}\rightarrow[r]}$ there exist ${x,y\in{\mathbb N}}$ such that ${\chi(x)=\chi(y)=\chi(x+y)=\cdots=\chi(x+ky)}$.

Equivalently, for any finite coloring of ${{\mathbb N}}$ there exists a monochromatic solution to the system ${x_{i+1}-x_i=x_0}$ for ${i=1,\dots,k-1}$.

Another consequence of Rado’s theorem is the following result, sometimes called Folkman’s theorem, which contains Schur’s theorem as a special case when ${k=2}$: \href{Folkman’s theorem}} For any ${r,k\in{\mathbb N}}$ and any function ${\chi:{\mathbb N}\rightarrow[r]}$ there exist ${x_1,\dots,x_k\in{\mathbb N}}$ and a color ${i\in[r]}$ such that

$\displaystyle \chi\left(\sum_{j\in\alpha}x_j\right)=i\qquad\forall\emptyset\neq\alpha\subset[k]$

While it’s not as immediate as the previous theorems, one can also formulate Folkman’s theorem in the form “For any finite coloring of ${{\mathbb N}}$ there exists a monochromatic solution to the system ${A\vec x=\vec 0}$“. To see that, let ${m=2^k-k-1}$ be the number of subsets of ${[k]}$ with at least two elements. Take ${A_1}$ to be the ${m\times k}$ matrix which contains in each line the indicator function of a subset ${\alpha\subset[k]}$ with ${|\alpha|\geq2}$. Then let ${A_2=-I_m}$ where ${I_m}$ is the ${m\times m}$ identity matrix. Finally let ${A}$ be the ${m\times(k+m)}$ concatenation of ${A_1}$ with ${A_2}$. For instance, when ${k=3}$ we get

$\displaystyle A=\left[\begin{array}{cccccccc}1&1&0&|&-1&0&0&0\\ 1&0&1&|&0&-1&0&0\\ 0&1&1&|&0&0&-1&0\\ 1&1&1&|&0&0&0&-1\end{array}\right]$

More generally, given an homogeneous system of linear equations ${A\vec x=\vec 0}$, where ${\vec x\in{\mathbb N}^d}$, ${\vec 0\in{\mathbb Z}^k}$ and ${A}$ is a ${k\times d}$ matrix with integer coefficients, one can ask whether for any finite coloring of ${{\mathbb N}}$ there exists a vector ${\vec x\in{\mathbb N}^d}$ with all coordinates in one color and such that ${A\vec x=\vec 0}$. The answer is provided by Rado’s theorem. Continue reading

Posted in Ramsey Theory | Tagged , , , | 2 Comments

## Hales-Jewett and a generalized van der Warden Theorems

The Hales-Jewett theorem is one of the most fundamental results in Ramsey theory, implying the celebrated van der Waerden theorem on arithmetic progressions, as well an its multidimensional and IP versions. One interesting property of the Hales-Jewett’s theorem is that it is a set theoretical statement, having no structure, and hence making it versatile for applications. Recently I realized that there exists an equivalent formulation of this theorem using some algebraic structure, and indeed it can be seen as an analogue of van der Waerden’s theorem. The main purpose of this post is to establish that equivalence. In an initial section I present the deduction of the multidimensional van der Waerden from the Hales-Jewett theorem, both to set the mood and to set the stage to later establish the analogy between van der Waerden’s theorem and the equivalent formulation of the Hales-Jewett theorem. Continue reading

## The restricted isometry property.

I have recently worked on a paper about RIP matrices, and decided to learn better about these objects. This post is the adaptation of some notes I wrote on the subject.

Let ${K be natural numbers. A vector ${x\in{\mathbb R}^n}$ is ${K}$-sparse if it has at most ${K}$ non-zero entries.

Definition 1 (RIP matrices) Let ${n>m}$ be positive integers and let ${\Phi}$ be a ${m\times n}$ matrix with real entries, let ${\delta>0}$ and let ${K be an integer. We say that ${\Phi}$ is ${(K,\delta)}$-RIP if for every ${K}$-sparse vector ${x\in{\mathbb R}^n}$ we have

$\displaystyle (1-\delta)\|x\|\leq\|\Phi x\|\leq(1+\delta)\|x\|$

Thus ${\Phi}$ acts almost as an isometry when we restrict our attention to ${K}$-sparse vectors.

The restricted isometry property is perhaps the simplest’ property of a matrix which makes it good’ for compressed sensing. It appeared as part of the outcome of a series of papers by Donoho, and CandèsRombergTao in 2004-2006 where other slightly different properties were studied (see these papers and also this survey). The earliest appearance of the name RIP that I could find was here, but even there the exact property is a little different from the modern one (which first appeared, I believe, here). Continue reading

Posted in Compressed Sensing | 1 Comment