Search

For $k \in \mathbb{N}$, write $S(k)$ for the largest natural number such that there is a $k$-colouring of $\{1,\dots,S(k)\}$ with no monochromatic solution to $x-y=z^2$. That $S(k)$ exists is a result of Bergelson, and a simple example shows that $S(k) \geq 2^{2^{k-1}}$. The purpose of this note is to show that $S(k)\leq 2^{2^{2^{O(k)}}}$., Comment: 6pp; for Endre Szemeredi's 80th Birthday volume

Suppose that $A$ is a $k \times d$ matrix of integers and write $\mathfrak{R}_A:\mathbb{N} \rightarrow \mathbb{N}\cup \{ \infty\}$ for the function taking $r$ to the largest $N$ such that there is an $r$-colouring $\mathcal{C}$ of $[N]$ with $\bigcup_{C \in \mathcal{C}}{C^d}\cap \ker A =\emptyset$. We show that if $\mathfrak{R}_A(r)<\infty$ for all $r \in \mathbb{N}$ then $\mathfrak{R}_A(r) \leq \exp (\exp(r^{O_{A}(1)}))$ for all $r \geq 2$. When the kernel of $A$ consists only of Brauer configurations -- that is vectors of the form $(y,x,x+y,\dots,x+(d-2)y)$ -- the above has been proved by Chapman and Prendiville with good bounds on the $O_A(1)$ term., Comment: 23 pp; corrections and an additional explanatory example from a referee

We establish various results including the following: if $1

For G a finite non-Abelian group we write c(G) for the probability that two randomly chosen elements commute and k(G) for the largest integer such that any k(G)-colouring of G is guaranteed to contain a monochromatic quadruple (x,y,xy,yx) with xy not equal to yx. We show that c(G) tends to 0 if and only if k(G) tends to infinity., Comment: 7pp; corrected typos

We show that there is an absolute $c>0$ such that any subset of $\mathbb{F}_2^\infty$ of size $N$ is $O(N^{1-c})$-stable in the sense of Terry and Wolf. By contrast a size $N$ arithmetic progression in the integers is not $N$-stable., Comment: 9 pp; corrected some errors and expanded the introduction

We show that if $G$ is a discrete Abelian group and $A \subset G$ has $\|1_A\|_{B(G)} \leq M$ then $A$ is $O(\exp(\pi M))$-stable in the sense of Terry and Wolf., Comment: 9pp; corrections and improvements following report by referee

We show that if G is a finite group and f is a {0,1}-valued function on G with Fourier algebra norm at most M then f may be computed by a coset decision tree (that is a decision tree in which at each vertex we query membership of a given coset) having at most \exp(\exp(\exp(O(M^2)))) leaves. A short calculation shows that any {0,1}-valued function which may be computed by a coset decision tree with m leaves has Fourier algebra norm at most \exp(O(m))., Comment: 28pp; corrections and typos

We show that if $f$ is an integer-valued function with spectral norm at most $M$ then there are subspaces $V_1,\dots,V_L$ and signs $\sigma_1,\dots,\sigma_L \in \{-1,1\}$ such that $f=\sigma_1 1_{V_1} + \dots + \sigma_L 1_{V_L}$ where $L < \exp(M^{3+o(1)})$. This note extracts out the argument from arXiv:1610.07092 to the model setting of $\mathbb{F}_2^n$. The hope is that it will clarify the arguments of that paper., Comment: 11 pp, corrected some errors

We show that if A is a finite set of integers then it has a subset S of size \log^{1+c} |A| (c>0 absolute) such that s+s' is never in A when s and s' are distinct elements of S., Comment: 47 pages. Corrections and clarifications

We show that if f is an injection from an n-dimensional Boolean cube (considered as an additive group) to a group of prime order then the probability that f(x+y)=f(x)+f(y) is O(2^{-n/11})., Comment: 7 pages, added an example to section 2, corrected some errors

We show that if G is a finite group and A is a subset of G with no non-trivial solutions to xz=yy then |A| < |G|/(log log |G|)^c., Comment: 27pp

We discuss a statistical variant of Ruzsa's covering lemma and use it to show that if G is an Abelian group of bounded exponent and A in G has |A+A| < K|A| then the subgroup generated by A has size at most exp(O(K log^22K))|A|, where the constant in the big-O depends on the exponent of the group only., Comment: 18pp

We show that if $G$ is a finite Abelian group and $f$ is an integer-valued map on $G$ with algebra norm at most $M$ then there is some $L < \exp(M^{4+o(1)})$, cosets of (possibly different) subgroups $W_1,...,W_L$, and $s_1,...,s_L \in \{-1,1\}$ such that $f=\sum_i{s_i1_{W_i}}$., Comment: 55pp; corrected arXiv title

Let $\mathbb{F}$ be a fixed finite field, and let $A \subset \mathbb{F}^n$. It is a well-known fact that there is a subspace $V \leq \mathbb{F}^n$, $\mbox{codim} V \ll_{\delta} 1$, and an $x$, such that $A$ is $\delta$-uniform when restricted to $x + V$ (that is, all non-trivial Fourier coefficients of $A$ restricted to $x + V$ have magnitude at most $\delta$). We show that if $\mathbb{F} = \mathbb{F}_2$ then it is possible to take $x = 0$; that is, $A$ is $\delta$-uniform on a subspace $V \leq \mathbb{F}^n$. We give an example to show that this is not necessarily possible when $\mathbb{F} = \mathbb{F}_3$. ADDED July 2016: shortly after this paper appeared on the arxiv, F. Manners showed us a rather short argument he had found in 2013, giving a better bound for our main theorem. We do not, therefore, intend to publish this note. The example over $\mathbb{F}_3$ may still be of interest to some readers and so we will not withdraw the paper from the arxiv., Comment: 4 pages

Suppose that $\mathbb{F}_p$ is coloured with $r$ colours. Then there is some colour class containing at least $c_r p^2$ quadruples of the form $(x, y , x + y, xy)$., Comment: 48 pages, accepted for publication in Discrete Analysis. Second version has minor changes arising from the referee report. Third version updated to DAJ format. in Discrete Analysis 2016:5

In this article we survey some of the recent developments in the structure theory of set addition., Comment: 38pp

We prove the following result due to Hamidoune using an analytic approach. Suppose that A is a subset of a finite group G with |AA^{-1}| \leq (2-\varepsilon)|A|. Then there is a subgroup H of G and a set X of size O_\varepsilon(1) such that A \subset XH., Comment: 6pp

ECM survey article discussing the structure of subsets of Abelian groups which behave `a bit like' cosets (of subgroups)., Comment: 14pp

Our main result is that if A is a finite subset of an abelian group with |A+A| < K|A|, then 2A-2A contains an O(log^{O(1)} K)-dimensional coset progression M of size at least exp(-O(log^{O(1)} K))|A|., Comment: 28 pp. Corrected typos. Added appendix on model setting

We show that if A is a subset of {1,...,N} contains no non-trivial three-term arithmetic progressions then |A|=O(N/ log^{1-o(1)} N). The approach is somewhat different from that used in arXiv:1007.5444., Comment: 16 pp. Corrected the proof of the Croot-Sisask Lemma. Corrected typos. Updated references

We show that if A is a subset of {1,...,N} containing no non-trivial three-term arithmetic progressions then |A|=O(N/ log^{3/4-o(1)} N)., Comment: 29 pp. Corrected typos. Added definitions for some non-standard notation and remarks on lower bounds

We investigate the size of subspaces in sumsets and show two main results. First, if A is a subset of F_2^n with density at least 1/2 - o(n^{-1/2}) then A+A contains a subspace of co-dimension 1. Secondly, if A is a subset of F_2^n with density at least 1/2-o(1) then A+A contains a subspace of co-dimension o(n)., Comment: 10 pp. Corrected typos

Suppose that G is an abelian group, A is a finite subset of G with |A+A|< K|A| and eta in (0,1] is a parameter. Our main result is that there is a set L such that |A cap Span(L)| > K^{-O_eta(1)}|A| and |L| = O(K^eta log |A|). We include an application of this result to a generalisation of the Roth-Meshulam theorem due to Liu and Spencer., Comment: 13 pp. Slightly refined the proof of Theorem 1.3. Replaced finite fields of characteristic 3 with arbitrary finite fields. Update references. Corrected typos

We show that if G is a group and A is a finite subset of G with |A^2| < K|A|, then for all k there is a symmetric neighbourhood of the identity S with S^k a subset of A^2A^{-2} and |S| > exp(-K^{O(k)})|A|., Comment: 5 pp. Corrected typos. Minor revisions

We develop a version of Freiman's theorem for a class of non-abelian groups, which includes finite nilpotent, supersolvable and solvable A-groups. To do this we have to replace the small doubling hypothesis with a stronger relative polynomial growth hypothesis akin to that in Gromov's theorem (although with an effective range), and the structures we find are balls in (left and right) translation invariant pseudo-metrics with certain well behaved growth estimates. Our work complements three other recent approaches to developing non-abelian versions of Freiman's theorem by Breuillard and Green, Fischer, Katz and Peng, and Tao., Comment: 21 pp. Corrected typos. Changed title from `From polynomial growth to metric balls in monomial groups'

Suppose that G is a finite group and A is a subset of G such that 1_A has algebra norm at most M. Then 1_A is a plus/minus sum of at most L cosets of subgroups of G, and L can be taken to be triply tower in O(M). This is a quantitative version of the non-abelian idempotent theorem., Comment: 82 pp. Changed the title from `Indicator functions in the Fourier-Eymard algebra'. Corrected the proof of Lemma 19.1. Expanded the introduction. Corrected typos

We show that if A is a finite subset of an abelian group with additive energy at least c|A|^3 then there is a subset L of A with |L|=O(c^{-1}\log |A|) such that |A \cap Span(L)| >> c^{1/3}|A|., Comment: 5 pp. Included refinement from c^{1/2} to c^{1/3}, independently discovered by Shkredov and Yekhanin in arXiv:1004.2294. Corrected typos

We provide further explanation of the significance of a construction in a recent paper of Wolf [Israel J. Math. 179 (2010), 253-278] in the context of the problem of finding large subspaces in sumsets., Comment: 4pp. Updated references. Corrected typos

We show that if A is a subset of Z_4^n containing no three-term arithmetic progression in which all the elements are distinct then |A|=o(4^n/n)., Comment: 24 pp. Corrected typos. Updated references. Minor revisions.

Suppose that G is a discrete abelian group and A is a finite symmetric subset of G. We show two main results. i) Either there is a set H of O(log^c|A|) subgroups of G with |A \triangle \bigcup H| = o(|A|), or there is a character X on G such that -wh{1_A}(X) >> log^c|A|. ii) If G is finite and |A|>> |G| then either there is a subgroup H of G such that |A \triangle H| = o(|A|), or there is a character X on G such that -wh{1_A}(X)>> |A|^c., Comment: 21 pp. Corrected typos. Minor revisions

We prove a Freiman-type theorem for locally compact abelian groups. If A is a subset of a locally compact abelian group with Haar measure m and m(nA) < n^dm(A) for all n>d log d then we describe A in a way which is tight up to logarithmic factors in d., Comment: 12 pp. Corrected typos. Updated references. Minor revisions.

We show two results. First, a refinement of Freiman's theorem: if A is a finite set of integers and |A+A| < K|A|, then A is contained in a multidimensional progression of dimension at most O(K^{7/4} log^3K) and size at most exp(O(K^{7/4} log^3K))|A|. Secondly, an improvement of a result of Konyagin and Laba: if A is a finite set of reals and a is a transcendental then |A+aA| >> |A|(log |A|)^{4/3-\epsilon} for all \epsilon>0., Comment: 11 pp. Corrected typos

Suppose that A is a subset of {1,...,N} such that the difference between any two elements of A is never one less than a prime. We show that |A| = O(N exp(-c(log N)^{1/4})) for some absolute c>0., Comment: 19 pp. Corrected typos. Updated references.