55

If $p$ is an odd prime (EDIT: other than 5) for which $-1$ is a quadratic residue mod $p$, and $A$ is the set of non-zero quadratic non-residues mod $p$, then $A+A$ is all of ${\bf Z}/p{\bf Z}$, whilst $A+AA$ is ${\bf Z}/p{\bf Z} \backslash \{0\}$. So counterexamples exist in finite fields, which rules out some methods of proof (e.g. "Ruzsa calculus" by ...

43

The set $X$ doesn't have to be the set of non-negative integers. This was known already to Härtter and Zöllner in 1977, who constructed an $X$ of the form $\{ 0, 1, 2, \ldots \} \setminus S $ for an infinite $S$.
For any $\varepsilon>0$, Erdös and Nathanson proved the existence of a set $X$ with $|X \cap [0,n]| = O(n^{\frac{3}{4} +\varepsilon})$, so ...

43

It seems that every squared finite group is indeed trivial.
Let $G$ be a squared finite group with the subset $A$ showing the squared-ness of $G$.
For any irreducible representation $\pi$ of $G$, denote $u_\pi = \sum_{g\in A} \pi(g) \in \operatorname{End} V_\pi$ where $V_\pi$ is the vector space of the representation. Then, by the condition on $A$, we have $...

40

There are many accounts of the truly exceptional breadth, depth and ingenuity of Jean's work and the quickness of his mind. These accounts are not exaggerations or embellishments. Jean collected nearly every honor and prize possible, including the Fields medal and Breakthrough prize. Even considering this, it is hard not to think that in some ways the weight ...

36

Let $n_0$ be the smallest number such that the sum of the reciprocals of the integers from $n_0+1$ to $n$ is $<2$. It is easy to see that $n_0 \approx n/e^2$, since $\sum_{j>n/e^2}^{n} 1/j \approx \log n - \log (n/e^2)
=2$. Now for any subset $A$ of $\{n_0 +1, \ldots, n\}$ either the sum of the reciprocals of elements in $A$ or the sum of the ...

34

Bourgain has made so many contributions to analysis. I will describe just a few of my favorites in harmonic analysis, and mention a few in number theory. First to cover my bases, I will name what I think he is best known for in harmonic analysis and are so significant that they do not fit your criteria:
Progress on Stein's restriction conjecture and on the ...

30

Van Vu and I coined the term in our book because there did not seem to be a widely adopted name for it previously. (Gowers, for instance, refers to "number of additive quadruples" rather than "additive energy", but this seemed to be too unwieldy to use for our purposes.) I think we settled on "energy" due to the vaguely quadratic nature of the expression, ...

answered Nov 18 '15 at 20:20

Terry Tao

83.1k2424 gold badges318318 silver badges399399 bronze badges

29

The answer is yes. Here is another example,
$$
x=2021231^2, \qquad d=82153503191760.
$$
Then
$$
x+d=9286489^2, \qquad
x+2d=12976609^2, \qquad
x+4d=18240049^2.
$$
Basically, write $x=X^2$, $x+d=Y^2$, $x+2d=Z^2$, and $x+4d=W^2$. Eliminating $x$ and $d$ reduces to the two equations:
$$
X^2-2Y^2+Z^2=0, \qquad
3X^2-4Y^2+W^2=0.
$$
This pair of equations defines a ...

26

If you fix $m$, this is known as the $m$-dimensional multiplication problem. In 2010 Koukoulopoulos showed that as $n\rightarrow \infty$ $$P(m,n)=\left|\lbrace a_1\cdots a_m\ :\ a_i\leq n \text{ for all } \ i\rbrace\right|\asymp \frac{n^{m+1}}{(\log n)^{c_m}(\log\log n)^{3/2}}$$ where $$c_{m}=\int_{1}^{\frac{k}{\log(m+1)}}\log x\text{d}x=\frac{\log(m+1)+m\...

24

I think, as implicitly suggested by Yemon Choi, it is possible to explain the proof of the answer of user49822 by making more use of idempotents. Suppose that the finite group $G$ is squared via the subset $A$. The element
$ e = \frac{1}{|G|}\sum_{g \in G} g$ is a primitive idempotent of $\mathbb{C}G.$
Let $ f= \frac{1}{|A|}\sum_{a \in A} a.$ Then we have $...

21

One of the best places to track these things down is The mathematical coloring book, by Alexander Soifer, Springer 2009. Chapter 35 is on "Monochromatic arithmetic progressions", and section 35.4, "Paul Erdős’s Favorite Conjecture", is on the problem you ask about.
As far as I can tell, the question is sometimes called the Erdős-Turán conjecture for two ...

answered Jun 3 '13 at 20:58

Andrés E. Caicedo

29.9k55 gold badges109109 silver badges196196 bronze badges

21

Here is a concrete counterexample (where $\mathbb{N}$ is the set of positive integers):
$$V:=\mathbb{N}\setminus\{a^2b^2+b:a,b\in\mathbb{N}\}.$$
It is straightforward to see that $V$ has density $1$, but it does not contain an infinite arithmetic progression.

20

Following marshall's comment below, I (sadly) had to completely re-write my original answer.
A famous open conjecture of Paul Erdos, first stated about 80 years ago, is that if all subset sums of an integer set $S\subset[1,n]$ are pairwise distinct, then $|S|<\log_2n+O(1)$ as $n\to\infty$. (Here $\log_2$ denotes the base-$2$ logarithm.) In modern terms, ...

20

It follows from results in Bourgain's Acta 1984 paper (but I have the impression these results were announced some years ealier?) that the dual of the disc algebra $A({\bf D})$ has cotype 2; and every bounded linear map from $A({\bf D})$ to a Banach space of cotype 2 is 2-summing. As a corollary, the canonical injection $A({\bf D}) \hat\otimes A({\bf D}) \to ...

18

About three years after posting this question, the answer is now known (although there still can be some room for improvements). Namely, Lemma 1 from a recent joint paper by Ernie Croot, Peter Pach, and myself reads as follows:
Suppose that $n\ge 1$ and $d\ge 0$ are integers, $P$ is a multilinear
polynomial in $n$ variables of total degree at most $d$ ...

18

Here is a small observation, generalizing Lucia's comment.
Proposition. If $A$ is a set of real numbers with minimal distance at least $1$, then $$|A+AA| \geq \frac{|A|(|A|-1)}{2}\geq |A+A|-|A|.$$
Proof. Let $r_m>\dots>r_1>0$ be the positive elements of $A$. Then the subsets $r_i+r_m A$ of $A+AA$ are pairwise disjoint, because $r_i+r_ma=r_j+r_ma'$ ...

18

Such sequences are called sum free sequences. In the paper "On a question about sum-free sequences", Deshouillers, Erdős and Melfi construct a sequence where $a_n$ is $o(n^{3+\epsilon})$. Luczak and Schoen, later improved this to a construction of a sum free sequence with $a_n=o(n^{2+\epsilon})$, and show that the exponent $2$ is minimal.
I should mention ...

answered Aug 31 '16 at 14:55

Gjergji Zaimi

79.1k44 gold badges205205 silver badges367367 bronze badges

18

The bound proposed by Lucia is correct. I add some detail and I stress that It is an application of "large deviation" theorem which is very very standard.
Set the following independent Bernoulli random variable defined as $$X_i=\begin{cases} 0 \text{ with } p=1/2\\ \frac{1}{i} \text{ with } p=1/2\end{cases}$$
Then we have the number of subset is given by
$$ ...

18

No. See for instance Exercise 2.3.5 of
Tao, Terence; Vu, Van H., Additive combinatorics, Cambridge Studies in Advanced Mathematics 105. Cambridge: Cambridge University Press (ISBN 978-0-521-13656-3/pbk). xviii, 512 p. (2010). ZBL1179.11002.
See also a number of papers of Ruzsa constructing various counterexamples, e.g.
Ruzsa, I.Z., On the number of ...

answered Oct 25 '17 at 23:19

Terry Tao

83.1k2424 gold badges318318 silver badges399399 bronze badges

17

Yet another concrete counterexample:
$$ \bigcup_{n=1}^\infty [n^3+n,(n+1)^3]. $$
More generally, any set containing arbitrarily long gaps is free of infinite arithmetic progressions, and has natural density $1$ if the gaps are properly spaced.
Incidentally, an incomparably subtler question is whether any set of positive natural density contains ...

17

Unfortunately such a simple converse cannot be possible because
one can "plant" long arithmetic progressions in $A$ while keeping it
sparse overall. For example, let $A$ consist of all integers of the form
$10^{n!}+m$ with $1 \leq m \leq n$ (which even makes $\sum_{n\in A} 1 / \log n$
converge).
[I see that GH from MO posted a very similar answer ...

answered Nov 5 '20 at 23:56

Noam D. Elkies

68.3k1212 gold badges244244 silver badges328328 bronze badges

16

This is a notorious problem. It is my impression that a lot of talent people have looked at it, without much progress. Ben Green has an excellent talk on the topic (in part) which can be viewed here: http://kva.screen9.tv/#gipkF4pTSbAL16tJjJzj8Q.
There is nothing special about constant 10 in the statement in Tao and Vu's book. It is generally believed that $...

16

You are essentially asking for quantitative estimates on Szemerédi's theorem, which states that the largest subset of $[1,n]$ without a k-term arithmetic progression has size $o(n)$. To be precise, let us define $r_k(n)$ to be the largest subset of [1,n] with no k-term arithmetic progression. Then a construction due to Behrend (essentially projecting a high-...

16

In fact this question was already asked at MO, although in disguise: see here. Richard Stanley answered it wonderfully. The champions are the nearest integers to $n(n+1)/4$.
For a quick proof, see Lemma 6.13 on Page 93 (and the preliminaries on Page 92) in Stanley's Topics in algebraic combinatorics.

16

One does not need Gaussians in the finite case, just take $f$ to be the indicator function of the interval $[-(n-1),n-1]\subset\mathbb F_p$. A simple computation gives
$$ |\hat f(x)| = \frac1{\sqrt p} \frac{|\sin\pi(2n-1)x/p|}{|\sin\pi(x/p)|} < \frac1{2\sqrt p\|x/p\|}, $$
where $\|x/p\|$ is the distance to $x/p$ from the nearest integer. As a result,
...

16

Answer to Question 1. Yes, $E(\mathbb{Z})=F$.
The inclusion $F\subseteq E(\mathbb{Z})$ follows from $E\subseteq E(\mathbb{Z})$ and Dickson's result $E=F$. It remains to show $E(\mathbb{Z})\subseteq F$. Pick $n\in E(\mathbb{Z})$. By definition there exist $u,v\in\mathbb{Z}^3$ such that $\lVert u\rVert=\lVert v\rVert$ and $n=\lVert u\rVert^2+\lvert u\cdot v\...

nt.number-theory co.combinatorics additive-combinatorics computational-number-theory sums-of-squares

16

One body of works which I found mind Boggling is related to the question: "Can you hear the degree of a map". I think the general theme is about the connection between Fourier analysis and algebraic topology. The beautiful videotaped lecture by Haim Brezis is about this topic. On the negative side, Bourgain and Kozma's paper One cannot hear the winding ...

16

It is not true. Take, for example, $A=\bigcup_{n\in\mathbb{N}}\{n^3,n^3+1,\dots,n^3+n\}$.

15

I believe there is an "energy" version of the conjectural inequality $|A+AA| \geq |A+A|$ which may explain why it was intuitive that there should be an "easy" proof of that inequality. Namely:
Proposition Let $A$ be a finite collection of nonzero elements of a field $F$. Let $a_1,a_2,a_3,a'_1,a'_2,a'_3$ be chosen uniformly and independently from $A$. ...

answered Apr 29 '15 at 16:09

Terry Tao

83.1k2424 gold badges318318 silver badges399399 bronze badges

15

It seems what you are asking is "If we have a precise asymptotic for the number of elements of a set, can we solve binary additive problems involving that set?"
The answer in general seems to be `no'. Let's consider Goldbach's conjecture that every large integer $n$ is the sum of two primes. It is not hard to see from pigeonholing that the typical $...

nt.number-theory analytic-number-theory prime-numbers additive-combinatorics computational-number-theory

Only top voted, non community-wiki answers of a minimum length are eligible

#### Related Tags

additive-combinatorics × 507nt.number-theory × 248

co.combinatorics × 225

reference-request × 46

sumsets × 43

gr.group-theory × 33

arithmetic-progression × 32

analytic-number-theory × 29

finite-groups × 24

prime-numbers × 21

finite-fields × 20

discrete-geometry × 16

pr.probability × 15

sidon-sets × 15

fourier-analysis × 12

ramsey-theory × 12

linear-algebra × 11

ca.classical-analysis-and-odes × 10

extremal-combinatorics × 9

fa.functional-analysis × 8

sequences-and-series × 8

semigroups-and-monoids × 8

partitions × 8

diophantine-equations × 7

computational-number-theory × 7