56
votes

### Is the set $ AA+A $ always at least as large as $ A+A $?

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}$, ...

- 92.8k

43
votes

Accepted

### Lagrange four squares theorem

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 ...

- 9,384

43
votes

### Is each squared finite group trivial?

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$, ...

- 1,676

42
votes

### Jean Bourgain's relatively lesser known significant contributions

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 ...

Community wiki

36
votes

Accepted

### Sets of unit fractions with sum $\leq 1$

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 \...

- 42.6k

34
votes

### Jean Bourgain's relatively lesser known significant contributions

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 ...

Community wiki

34
votes

Accepted

### A proof of Van der Waerden's theorem using a weakened form of Szemeredi's theorem

As (implicitly) observed already in Szemerédi's celebrated paper
Szemerédi, Endre, On sets of integers containing no (k) elements in arithmetic progression, Acta Arith. 27, 199-245 (1975). ZBL0303....

- 92.8k

33
votes

Accepted

### Where did the term "additive energy" originate?

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 "...

- 92.8k

25
votes

Accepted

### Is each squared finite group trivial?

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 ...

Community wiki

23
votes

Accepted

### Size of set of integers with all sums of two distinct elements giving squares

The size of such sets is bounded by some (unknown) constant, assuming a big conjecture in arithmetic geometry.
The Bombieri-Lang conjecture (non-trivially via the Uniformity Conjecture, see Stanley ...

- 5,978

23
votes

Accepted

### Sets with both additive and multiplicative gaps

I can give an upper bound of $2p/5$ and a lower bound of $(2/5-o(1))p$ for a conjecturally infinite set of $p$.
For the upper bound, the numbers $z, z+1, 2z+2, 2z+1, 2z$ form a pentagon in your graph ...

- 119k

21
votes

### Is there a set of positive integers of density 1 which contains no infinite arithmetic progression?

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$, ...

- 87k

20
votes

### Jean Bourgain's relatively lesser known significant contributions

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 ...

Community wiki

19
votes

### Size of set of integers with all sums of two distinct elements giving squares

"D15 Numbers whose sums in pairs make squares" in Guy, Unsolved Problems in Number Theory, 3rd ed., credits Erdos and Leo Moser with asking "are there, for every $n$, $n$ distinct ...

- 36.5k

19
votes

Accepted

### Does $A-A=\mathbb Q$ hold for $A=\{x^4+y^4:\ x,y\in\mathbb Q\}$?

According to Tito Piezas's website $x^4+y^4-(z^4+t^4) = N$,
There is an identity
$((2a+b)c^3d)^4 + (2ac^4-bd^4)^4 - (2ac^4+bd^4)^4 - ((2a-b)c^3d)^4 = a(2bcd)^4$
where $b = c^8-d^8$, for arbitrary {$a,...

- 1,079

18
votes

Accepted

### When does $P(a−b)=0$ for $a≠b$ ensure $P(0)=0$? (Continued.)

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, ...

- 21.8k

18
votes

### Is the set $ AA+A $ always at least as large as $ A+A $?

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|.$$
...

- 87k

18
votes

Accepted

### Is there a strictly increasing sequence such that it is o(2^n) and any term cannot equal the sum of any unrepeated predecessors?

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 ...

- 82.5k

18
votes

### Sets of unit fractions with sum $\leq 1$

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 ...

- 4,266

18
votes

Accepted

### Optimality of the Plünnecke-Ruzsa Inequality

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/...

- 92.8k

17
votes

### Is there an "analytical" version of Tao's uncertainty principle?

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 ...

- 21.8k

17
votes

### Is there a set of positive integers of density 1 which contains no infinite arithmetic progression?

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 ...

- 21.8k

17
votes

Accepted

### Converse to Erdős' conjecture on arithmetic progressions

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 ...

- 72.6k

17
votes

Accepted

### Sets that are not sum of subsets

There are three questions in the OP, and I'll try to address each of them in as comprehensive a way as I can. I'll be glad to add in further details (and references) if requested.
◇ Preliminaries on ...

- 8,698

16
votes

Accepted

### Most dense subset of numbers that avoids arbitrarily long arithmetic progressions

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, ...

- 756

16
votes

### Is the set $ AA+A $ always at least as large as $ A+A $?

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:
...

- 92.8k

16
votes

Accepted

### Which of these sums appear most often?

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 ...

- 87k

16
votes

### Extension of Dickson's theorem on integers of the form $a^2+b^2+2c^2$

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$...

- 2,519

16
votes

### Jean Bourgain's relatively lesser known significant contributions

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 ...

Community wiki

16
votes

### Converse to Erdős' conjecture on arithmetic progressions

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

- 87k

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

#### Related Tags

additive-combinatorics × 592nt.number-theory × 278

co.combinatorics × 271

sumsets × 56

reference-request × 50

gr.group-theory × 40

arithmetic-progression × 39

analytic-number-theory × 31

finite-groups × 28

finite-fields × 25

prime-numbers × 21

pr.probability × 18

discrete-geometry × 17

sidon-sets × 15

linear-algebra × 14

fourier-analysis × 14

ramsey-theory × 13

polynomials × 11

semigroups-and-monoids × 11

extremal-combinatorics × 11

graph-theory × 10

ca.classical-analysis-and-odes × 10

integer-sequences × 10

fa.functional-analysis × 9

sequences-and-series × 9