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

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

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