Questions tagged [additive-combinatorics]

Questions on the subject additive combinatorics, also known as arithmetic combinatorics, such as questions on: additive bases, sum sets, inverse sum set theorems, sets with small doubling, Sidon sets, Szemerédi's theorem and its ramifications, Gowers uniformity norms, etc. Often combined with the top-level tags nt.number-theory or co.combinatorics. Some additional tags are available for further specialization, including the tags sumsets and sidon-sets.

Filter by
Sorted by
Tagged with
111 votes
7 answers
8k views

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

Let $A$ be a finite set of real numbers. Is it always the case that $|AA+A| \geq |A+A|$? My first instinct is that this is obviously true, and there is a one-line proof which I am foolishly ...
Oliver Roche-Newton's user avatar
62 votes
5 answers
9k views

Jean Bourgain's relatively lesser known significant contributions

Jean Bourgain passed away on December 22, 2018. A great mathematician is no longer with us. Terry Tao has blogged about Bourgain's death and mentioned some of his more recent significant contributions,...
58 votes
2 answers
4k views

For a finite set A of positive reals, prove that the set A + A - A contains at least as many positive as negative elements

I am currently working on a proof that would need to use the following theorem that I cannot prove: "Let $A$ be a finite set of positive real numbers. Then, the set $A + A - A$ contains at least ...
Timo Reichert's user avatar
56 votes
3 answers
5k views

Number of elements in the set $\{1,\cdots,n\}\cdot\{1,\cdots,n\}$

Let $A_n=\{a\cdot b : a,b \in \mathbb{N}, a,b\leq n\}$. Are there any estimates for $|A_n|$? Will it be $o(n^2)$?
Kamalakshya's user avatar
49 votes
3 answers
2k views

Is each squared finite group trivial?

A semigroup $S$ is defined to be squared if there exists a subset $A\subseteq S$ such that the function $A\times A\to S$, $(x,y)\mapsto xy$, is bijective. Problem: Is each squared finite group ...
Taras Banakh's user avatar
  • 40.7k
41 votes
4 answers
1k views

Sets of unit fractions with sum $\leq 1$

Consider a set of fractions $\left\{1, \frac{1}{2}, \frac{1}{3}, \ldots, \frac{1}{n}\right\}$. How many subsets of this set have sum at most 1? I'm interested in the asymptotics of this number. ...
Mikhail Tikhomirov's user avatar
39 votes
2 answers
2k views

Is number of different sums monotone?

Suppose you have a set $S$ consisting of $n$ different integers. Let $$W_k = \#\biggl\{x\in\Bbb Z\colon \text{there exists } T \subseteq S,\, \#T=k,\, \sum_{a \in T} a = x\biggr\}.$$ My question is: ...
ivmihajlin's user avatar
35 votes
3 answers
2k views

Lagrange four squares theorem

Lagrange's four square theorem states that every non-negative integer is a sum of squares of four non-negative integers. Suppose $X$ is a subset of non-negative integers with the same property, that ...
M. Farrokhi D. G.'s user avatar
35 votes
5 answers
4k views

Cliques, Paley graphs and quadratic residues

A question I've thought about, on and off for a long time, is how to improve the best bounds that (seem to be) known for the clique numbers of Paley graphs. If p=1 mod 4 is a prime, we can define the ...
Mike's user avatar
  • 703
31 votes
2 answers
3k views

The Erdős-Turán conjecture or the Erdős' conjecture?

This has been bothering me for a while, and I can't seem to find any definitive answer. The following conjecture is well known in additive combinatorics: Conjecture: If $A\subset \mathbb{N}$ and $$\...
Eric Naslund's user avatar
  • 11.2k
28 votes
3 answers
871 views

Ordering subsets of the cyclic group to give distinct partial sums

Suppose that you are given a set $S$ of $k$ nonzero elements from $\mathbb{Z}_n$. Is it always possible to order the elements of $S$, say $a_1,a_2,\dots,a_k$ in such a way that the partial sums $a_1,...
Ian Wanless's user avatar
27 votes
1 answer
2k views

Is every real number in [0,1] a product of three (or more) Cantor set's numbers?

It is well known that every number $x$ in the unit interval $[0,1]$ is the arithmetic mean of two elements of the (triadic) Cantor set $C$. The way to see it I like the most: the Cantor set is the ...
Pietro Majer's user avatar
  • 56.3k
26 votes
2 answers
1k views

Partitions to different parts not exceeding $n$

Consider the polynomial $(1+x)(1+x^2)\dots (1+x^n)=1+x+\dots+x^{n(n+1)/2}$, which enumerates subj. How to prove that it's coefficients increase up to $x^{n(n+1)/4}$ (and hence decrease after this)? Or ...
Fedor Petrov's user avatar
26 votes
1 answer
3k views

Monochromatic triangles in every two-coloring of the plane?

An old problem (possibly due to Erdős and Graham?): given a triangle $T$ and a two-coloring of the plane, does there necessary exist a monochromatic congruent copy of $T$? Here "monochromatic" means ...
Matthew Kahle's user avatar
26 votes
3 answers
2k views

long enough interval of integers to solve a simultaneous congruence

Let $a$, $b$ be two coprime natural numbers. Let $A \subseteq \{0,1,\ldots, a-1\}$ and $B \subseteq \{0,1,\ldots,b-1\}$ be two nonempty sets, which we think of as sets of residues mod $a$ and $b$ ...
Labrador's user avatar
  • 285
26 votes
1 answer
1k views

probability of zero subset sum

Almost 17 years ago, I asked the following question on USENET, motivated by a method in numerology (I kid you not). Pick integers $n \ge 2$, $k \ge 1$. Toss $n$ $k$-sided dice. The sides of each die ...
Brendan McKay's user avatar
26 votes
0 answers
898 views

Which sets of roots of unity give a polynomial with nonnegative coefficients?

The question in brief:   When does a subset $S$ of the complex $n$th roots of unity have the property that $$\prod_{\alpha\, \in \,S} (z-\alpha)$$ gives a polynomial in $\mathbb R[z]$ with ...
Louis Deaett's user avatar
  • 1,513
24 votes
3 answers
1k views

Are sets with similar asymptotic behavior as the primes necessarily finite additive bases?

The set of primes $\mathbb{P}$ has many interesting properties in additive number theory and some of the most famous open problems about $\mathbb{P}$ are the well-known Goldbach's strong and weak ...
Joni Teräväinen's user avatar
24 votes
1 answer
2k views

Arithmetic Progressions of Squares

Fermat may or may not have known that there are 3-term arithmetic progressions of squares (like $1^2, 5^2, 7^2$, and that there are no 4-term APs. Murky history aside, Keith Conrad has two pleasant ...
Kevin O'Bryant's user avatar
24 votes
2 answers
7k views

EGZ theorem (Erdős-Ginzburg-Ziv)

Erdős, Ginzburg and Ziv prove the following: Let $n \geq 1$ and $a_1,\ldots, a_{2n-1}\in \mathbb{Z}$. There exist distinct $i_1,\ldots , i_n$ such that $$ a_{i_1} + \cdots + a_{i_n} \equiv 0 \pmod{n}....
Portland's user avatar
  • 2,752
23 votes
2 answers
3k views

What is the minimal density of a set A such that A+A = N?

Thinking about the four square theorem and related questions, I found myself wondering: What is the minimal density of a set $A \subset \{0, 1, 2, ... \}$ such that $A + A = \mathbb{N}$? What I know: ...
Zur Luria's user avatar
  • 1,613
23 votes
3 answers
3k views

How many different numbers can be obtained as product of first $n$ natural numbers?

Let m and n be natural numbers, and consider the set of all possible products of m (not necessarily distinct) elements from the set $\{1,2,\ldots,n\}$, that is consider the set $\{1^{a_1} \cdot 2^{...
Hujdurovic's user avatar
23 votes
4 answers
3k views

What is the shortest route to Roth's theorem?

Roth first proved that any subset of the integers with positive density contains a three term arithmetic progression in 1953. Since then, many other proofs have emerged (I can think of eight off the ...
Thomas Bloom's user avatar
  • 6,608
23 votes
1 answer
795 views

integers which are sums of binomial coefficients: $\sum_i {n \choose k_i}$

Let $n$ be an integer. For $S$ a subset of $\{0,\dots,n\}$, define $$m(S) = \sum_{k \in S} {n \choose k}.$$ Let $M_n$ be the set of integers of the form $m(S)$ for all sets $S \subset \{0,\dots,n\}$. ...
Joël's user avatar
  • 25.7k
21 votes
1 answer
767 views

Avoiding multiples of $p$

Let $p$ be a prime number and $P=\{1,2,...,p-1\}$ In how many ways we can sum all the elements of $P$ in such a way that we will reach a multiple of $p$ only when we sum the last summand? For ...
Konstantinos Gaitanas's user avatar
21 votes
4 answers
3k views

Arithmetic progressions inside polynomial sets

There are at most 3 perfect squares in arithmetic progression (Fermat, Euler). It was shown in [1] that if $n>2$ there are no three term arithmetic progression consisting of nth powers. Take a non-...
Manuel Silva's user avatar
20 votes
3 answers
1k views

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

Are there arbitrarily large sets $\mathcal S=\{a_1,\ldots,a_n\}$ of strictly positive integers such that all sums $a_i+a_j$ of two distinct elements in $\mathcal S$ are squares? Considering subsets in ...
Roland Bacher's user avatar
20 votes
3 answers
1k views

A sumset inequality

A friend asked me the following problem: Is it true that for every $X\subset A\subset \mathbb{Z}$, where $A$ is finite and $X$ is non-empty, that $$\frac{|A+X|}{|X|}\geq \frac{|A+A|}{|A|}?$$ Here ...
Eric Naslund's user avatar
  • 11.2k
19 votes
3 answers
1k views

The sum of integers being a bijection

What are the pairs $(P,Q)$ of subsets of $\mathbb N$ for which the map \begin{eqnarray*} P\times Q & \rightarrow & {\mathbb N} \\\\ (p,q) & \mapsto & p+q \end{eqnarray*} is a bijection ...
Denis Serre's user avatar
  • 51.5k
19 votes
3 answers
1k views

Can nonabelian groups be detected "locally"?

Suppose $m,n\geq 2$ are two integers. Is it true that for every sufficiently large nonabelian group $G$, one can find a set $A\subset G$, with $|A|=n$, so that $|A^m| >\binom{n+m-1}{m}$? (Edit) ...
Gjergji Zaimi's user avatar
19 votes
4 answers
856 views

Size of sets with complete double

Let $[n]$ denote the set $\{0,1,...,n\}$. A subset $S\subseteq [n]$ is said to have complete double if $S+S=[2n]$. Let $m(n)$ be the smallest size of a subset of $[n]$ with complete double. My ...
Hailong Dao's user avatar
  • 30.3k
19 votes
3 answers
1k views

An “Average” Erdős–Turán conjecture

Right, so the Erdős–Turán conjecture for additive bases (of order 2) says, with the usual notations, that $\sup r_B (n) = \infty$. Let’s look instead at the average number of representations, i.e.: ...
Peter Hegarty's user avatar
18 votes
4 answers
2k views

Number of vectors so that no two subset sums are equal

Consider all $10$-tuple vectors each element of which is either $1$ or $0$. It is very easy to select a set $v_1,\dots,v_{10}= S$ of $10$ such vectors so that no two distinct subsets of vectors $S_1 \...
Simd's user avatar
  • 3,195
18 votes
3 answers
1k views

Decomposing a finite group as a product of subsets

My friend Wim van Dam asked me the following question: For every finite group $G$, does there exist a subset $S\subset G$ such that $\left|S\right| = O(\sqrt{\left|G\right|})$ and $S\times S = G$? ...
Scott Aaronson's user avatar
18 votes
1 answer
572 views

Characterizing the elements of $(A-A)/(A-A)$, where $A$ is a Cantor-like subset of the integers

Short version of my question: I'm interested in the following fact. If $m,n$ are odd integers, then $m/n$ can be written as the ratio of two numbers of the form $\sum_{j=0}^\ell \epsilon_j 4^j$, ...
Alan C's user avatar
  • 503
18 votes
1 answer
869 views

Two conjectures about zero inner products and dissociated sets

The following problems come from something I worked on (with my coauthors) related to proving a new time lower bound for streaming problems. Having worked on these problems for some time with little ...
Simd's user avatar
  • 3,195
17 votes
3 answers
3k views

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

Let $p$ be a prime. For $f: \mathbb{Z}/p \mathbb{Z} \rightarrow \mathbb{C}$ let its Fourier transform be: $$\hat f(n) = \frac{1}{\sqrt{p}}\sum_{x \in \mathbb{Z}/p \mathbb{Z}} f(x)\, e\left(\frac{-xn}{...
Rodrigo's user avatar
  • 1,235
17 votes
2 answers
2k views

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

Van der Waerden's theorem states that any colouring of the integers in a finite number of colours has monochromatic arithmetic progressions of arbitrary length. Szemerédi's Theorem is a dramatic ...
Ivan Meir's user avatar
  • 4,762
17 votes
1 answer
661 views

Combinatorics problem about sum of natural numbers

Following combinatorics problem is claimed to be an open problem in "The Princeton Companion to Mathematics" (pp. 6) Let $a_1,a_2,a_3,...$ be a sequence of positive integers, and suppose that each $...
rationalbeing's user avatar
17 votes
1 answer
1k views

Sum and product estimate over integers, rationals, and reals

My question is the following: is finding a lower bound for $|A+A\cdot A|$ (as a function of $|A|$) where $A$ is any finite subset of the positive integers equivalent to finding the same lower bound ...
George Shakan's user avatar
16 votes
1 answer
2k views

Where did the term "additive energy" originate?

A fundamental object in modern additive combinatorics and harmonic analysis is additive energy. Given a subset $A$ of (say) an abelian group $G$ the additive energy of $A$ is defined to be the ...
Mark Lewko's user avatar
  • 11.7k
16 votes
2 answers
2k views

Sets that are not sum of subsets

Let $\mathcal P$ be the set of finite subsets of $\mathbb Z_{\geq 0}$ , each of them contains $0$. We say that $A \in \mathcal P$ is indecomposable if it is not $B+C$ (the sum set of $B,C$) with $B,C\...
Hailong Dao's user avatar
  • 30.3k
16 votes
2 answers
2k views

Roth's theorem and Behrend's lower bound

Roth's theorem on 3-term arithmetic progressions (3AP) is concerned with the value of $r_3(N)$, which is defined as the cardinality of the largest subset of the integers between 1 and N with no non-...
Yui Nishizawa's user avatar
16 votes
2 answers
956 views

The Stable Set Conjecture

A set $\mathcal S$ of positive integers is called stable if for every fixed positive integer $d$, the relation $$n\in \mathcal S \iff dn\in \mathcal S$$ holds for almost all positive integers $n$. ...
Sayan Dutta's user avatar
16 votes
1 answer
738 views

Corners theorem in finite fields

The corners theorem of Ajtai and Szemerédi states that if $A\subseteq[N]^2$ is corner-free, i.e. there are no $x,y,h\in\mathbb{N}$ with all of $(x,y),(x+h,y),(x,y+h)$ in $A$, then $|A|=o(N^2)$. The ...
Tristan Shin's user avatar
16 votes
1 answer
451 views

Escaping from a centralizer

Let $G = Sym(n)$, $n$ even. Let $H<G$ be the stabilizer of the partition $\{\{1,2\},\{3,4\},\dotsc,\{n-1,n\}\}$, or, what is the same, the centralizer of $(1\;2) \dotsc (n-1\; n)$. By Stirling's ...
H A Helfgott's user avatar
  • 19.3k
15 votes
2 answers
712 views

Subsets of $(\mathbb{Z}/p)^{\times n}$

There seems to be some combinatorial fact that every subset $A$ of $G=(\mathbb{Z}/p)^{\times n}$ of cardinality $\frac{p^n-1}{p-1}+1$ containing $\vec{0}$ satisfies $(p-1)A=G$. ($p$ is a prime number....
Adam Chapman's user avatar
15 votes
1 answer
823 views

Goldbach-type theorems from dense models?

I'm not a number theorist, so apologies if this is trivial or obvious. From what I understand of the results of Green-Tao-Ziegler on additive combinatorics in the primes, the main new technical tool ...
Harrison Brown's user avatar
15 votes
1 answer
970 views

Sets with both additive and multiplicative gaps

I feel that the following problem should have a clean and simple solution, but so far I couldn't find one. Suppose that $p$ is a prime, and that $A\subseteq\mathbb Z/p\mathbb Z$ is a set such that ...
Seva's user avatar
  • 22.8k
15 votes
4 answers
571 views

Are all partial consecutive harmonic subsums distinct?

Let $b \gt a \geq 0$ be integers, and as elsewhere let $H_n$ be $\sum^n_{i=1} 1/i$. A partial consecutive harmonic subsum is a number $H(a,b)$ of the form $H_b - H_a$ (with $ H_0=0$). If $c=a$ and $...
Gerhard Paseman's user avatar

1
2 3 4 5
14