77
votes
Accepted
For a finite set A of positive reals, prove that the set A + A - A contains at least as many positive as negative elements
Here is a counterexample. We first need a "more sums than differences" construction:
Lemma. For any $\varepsilon>0$ there exists a cyclic group ${\bf Z}/N{\bf Z}$ and a non-empty subset ...
- 114k
51
votes
Is number of different sums monotone?
A counterexample for the exact inequality: $S = \{1,2,3,4,7,8,9,10\}$. Then $W_3 = 22$ (we get the numbers $6, 7, \dotsc, 27$) and $W_4 = 21$ (we get $10$, $34$, and the numbers $13, 14, \dotsc, 31$).
- 1,531
46
votes
Accepted
Is number of different sums monotone?
This looks to be a surprisingly delicate problem. Some comments:
There is an easy lower bound $(n-k) W_k \leq n W_{k+1}$ for any $1 \leq k < n$. Indeed, any element $x$ of $W_k$ can contribute ...
- 114k
44
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 ...
44
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$, ...
- 2,178
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 ...
- 14.6k
38
votes
Accepted
What is the minimal density of a set A such that A+A = N?
Let $A_{\mathrm{even}}$ ($A_{\mathrm{odd}}$) be the set of integers whose binary expansion has $0$ at every even (odd, respectively) position, and $A=A_{\mathrm{even}}\cup A_{\mathrm{odd}}$. Then all ...
- 47.1k
37
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 \...
- 43.7k
36
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....
- 114k
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 ...
33
votes
What is the minimal density of a set A such that A+A = N?
It is easy to see that quadratic density is both required and sufficient. The question is then of the leading coefficient.
Let $A$ be such that $A+A = \mathbb{N}$, and let $A(n) = \lvert A \cap [0,n] \...
- 4,219
32
votes
Accepted
Is every real number in [0,1] a product of three (or more) Cantor set's numbers?
Yes, every real number $u \in [0,1]$ can be written as $u = x^2 y$ where $x,y \in C$ are in the Cantor set $C$. In particular, every real number in $[0,1]$ is a product of three Cantor set elements. ...
- 6,237
28
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 ...
27
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,567
25
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 ...
- 7,003
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 ...
- 148k
22
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$, ...
- 105k
22
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 ...
- 23k
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
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/...
- 114k
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 ...
- 39.9k
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,361
18
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 ...
- 10.5k
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 ...
- 23k
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 ...
- 79.9k
17
votes
Accepted
Subsets of $(\mathbb{Z}/p)^{\times n}$
There is an alternative elementary way to prove this and see where the number $\frac{p^n-1}{p-1}+1$ comes from.
Lemma: If $|A|\geq \frac{p^n-1}{p-1}+1$ then every point in $\mathbb F_p^n$ lies in a ...
- 85.5k
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 ...
- 105k
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,600
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
Accepted
Goldbach conjecture and other problems in additive combinatorics
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 ...
- 13k
Only top scored, non community-wiki answers of a minimum length are eligible