# Tag Info

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

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

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

• 1,079
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

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

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

• 21.8k
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
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
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

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

### 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
It is not true. Take, for example, $A=\bigcup_{n\in\mathbb{N}}\{n^3,n^3+1,\dots,n^3+n\}$.