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.
774 questions
0
votes
0
answers
12
views
What is the additive dimension of the Cantor set?
This is a question I have been working on for awhile with limited progress.
For $0 < \alpha < 1$, let $C_\alpha$ be the middle-$\alpha$ Cantor set, obtained by starting from $[0, 1]$ and ...
- 11.4k
-1
votes
1
answer
180
views
Extension of a basic result in additive combinatorics
Below is an apparently very basic result in additive combinatorics:
Let $A,B \subseteq \mathbb{Z}$ be finite sets. Let $A+B = \{a+b : a \in A, b \in B\}$ be their sum-set. Then $|A+B| \geq |A| + |B| - ...
- 31.7k
0
votes
0
answers
107
views
Are these additive representations of primes known? [closed]
While computing empirically with primes up to 10^8 (zero counterexamples found), I observed a chain of increasingly strong representations. A notable pattern: for each hypothesis, the number of ...
3
votes
1
answer
394
views
Natural numbers as sums of powers of distinct numbers #2
Find the smallest number $n$ such that almost all natural numbers can be represented as the sum $$a_1^{a_{p(1)}}+a_2^{a_{p(2)}}+\dots+a_n^{a_{p(n)}}$$ where $a_1,\dots,a_n$ are pairwise distinct ...
12
votes
1
answer
681
views
Is a Fourier-free presentation of Roth's proof of Roth's theorem possible?
Below is a purely combinatorial statement, that is (essentially) the key step in Roth's celebrated proof of Roth's theorem on arithmetic progressions.
Let $n$ be a large integer and $A \subseteq Z_n$ ...
- 14.2k
2
votes
1
answer
182
views
Minimum degree in a graph defined by sumsets
I have the following conjecture.
Conjecture. Let $A$ be a finite set in some abelian group $G$, and let $A = B\cup B'$ be a partition of $A$ into two disjoint nonempty sets. We define a graph on the ...
- 1,373
4
votes
0
answers
155
views
Subgroup of index 2 of a field, which avoids products of finite sets
Let $Q$ be a countable field with characteristic $2$. E.g. we could take $Q=\mathbb{F}_2(x)$, the rational functions over the two element field $\mathbb{F}_2$, but other fields are fine too. Is there ...
- 13.9k
8
votes
0
answers
461
views
$1$-dimension reduction of Erdős Problem 86
Let $n<N$ be natural numbers. Take $A\subset\mathbb{Z}/N\mathbb{Z},|A|=n$, we build a graph $G_{n,N,A}$ with vertex set $E=\{-1,0,1\}\times\mathbb{Z}/N\mathbb{Z}$, $(1,x)$ adjacent with $(0,x-a)$, $...
- 1,190
1
vote
1
answer
159
views
Subsets $S_1,S_2$ of $\mathbb{F}_p$ with equal sum, such that $S_1\mathbin\Delta S_2$ intersects with a small fixed $T\subset \mathbb{F}_p$
$\newcommand\diff{\mathbin\Delta}$Let $p$ be a prime, $S\subseteq \mathbb{F}_p$ be a subset satisfying $2^{\#S}>p$. By the Dirichlet Box Principle, there exist distinct subsets $S_1,S_2\subset S$ ...
- 472
3
votes
1
answer
142
views
Partition of a $2n$-dimensional vector space into non-parallel $n$-dimensional affine subspaces
Problem. Let $\mathcal A$ be a family of pairwise disjoint $n$-dimensional affine subspaces covering a $2n$-dimensional vector space over a finite field. Are any affine subspaces $A,B\in\mathcal A$ ...
- 46.2k
7
votes
1
answer
323
views
Can $E + E$ and $E \cdot E$ have simultaneously small Hausdorff dimension?
Let $E$ be a subset of $\mathbb R$ with Hausdorff dimension $0 < \dim_H (E) < 1$.
We write $E + E$, $E \cdot E$ for the sets of sums and products of elements of $E$ respectively.
Question: Is it ...
- 11.4k
3
votes
0
answers
353
views
Five integers which sum in pairs to squares
This is the title of an article by A.R. Thatcher published in the Mathematics Gazette, Five Integers Which Sum in Pairs to Squares. There he published several solutions to the problem, including one ...
- 31.7k
2
votes
0
answers
168
views
Integers of the form $x_1+\ldots+x_k$ with $\mathrm{lcm}[x_1,\ldots,x_k]$ a product of $k$ consecutive integers
For any positive integer $k$, let us define $S(k)$ as the set of $x_1+\ldots+x_k$
with $x_1,\ldots,x_k$ positive integers such that $[x_1,\ldots,x_k]$ (the least common multiple of $x_1,\ldots,x_k$) ...
- 19.3k
4
votes
0
answers
136
views
Which (if any) of these sumset inequalities hold?
For finite subsets $A$ and $B$ of the real numbers, let $A+B$ denote the sumset $\{a+b : a\in A, b\in B\}$, and let $A\cdot B$ be the same thing but with multiplication. Let $hA$ be defined ...
- 1,373
3
votes
1
answer
271
views
A reformulation of lower bounds for R(k,k) via additive constraints in circulant 2-colorings — is this known?
Lower bounds for diagonal Ramsey numbers $R(k,k)$ are often obtained from highly symmetric $2$-colorings of complete graphs, such as circulant or Paley-type constructions.
While analyzing such ...
- 43