# Tag Info

## Hot answers tagged additive-combinatorics

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 ...
36 votes
Accepted

• 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

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