All Questions
21 questions
2
votes
0
answers
278
views
On $(k,\ell)$-sumfree sets
Call a set $\mathcal S \subset \mathbb N$ to be $(k,\ell)$-sumfree if there are no non-trivial solutions to the equation
$$x_1+\dots +x_k = y_1+\dots +y_\ell$$
in the set (for distinct $x_i$'s and $...
- 791
3
votes
1
answer
181
views
Decomposing a set of integers as a union of well-separated (discrete) intervals
Let a discrete interval be a set of the form $\{x \in \mathbb Z \colon a \le x \le b\}$ with $a, b \in \mathbb Z \cup \{\pm \infty\}$. Then define the boxing dimension $\text{bim}(S)$ of a set $S \...
- 10.5k
2
votes
0
answers
125
views
Almost subgroups of $\mathbb S^1$
Suppose $X\subset \mathbb S^1$ is a finite subset of the group $\mathbb S^1$ such that $|X+X|<(1+c )|X|$ for a sufficiently small $c\in(0,1)$. I believe that in such case there exists a subgroup $G=...
- 14.3k
3
votes
0
answers
93
views
"Skew-dimension" and discrete parallelepipeds
Let $(G,+)$ be an abelian group. Given a subset $B\subseteq G\setminus\{0\}$, define the "discrete span" of $B$, which I will denote $\langle B\rangle_d$, to be the set of all $\sum A$ for $...
6
votes
1
answer
458
views
Bounding size of partial difference sets given size of partial sumsets
In this paper by Katz and Tao, the following bounds were established.
Let $A,B$ be finite subsets of an abelian group, with $|A|,|B|\le N$. We fix some $G \subset A\times B$. We define $C = \{a+b:(a,b)...
- 3,499
7
votes
0
answers
203
views
Primitive recursive bounds for the the Gallai-Witt theorem
Let me first recall some facts:
By the work of Gowers, the Van der Waerden numbers belong to class $\mathcal{E}^3$ of the Grzegorczyk hierarchy
By the work of Shelah, the Hales-Jewett numbers belong ...
- 32.1k
3
votes
0
answers
62
views
Almost quadratic difference sets
Does there exist a characterization of sets $S$ such that $|S-S|$ is "almost quadratic" in $|S|$? For instance, what are some examples of sets such that $|S-S|$ is on the order of $\frac{{|S|}^2}{\log ...
- 31
1
vote
0
answers
80
views
Packing almost-subgroups into a group
We consider a group finite $G$. We say a set $A\subset G$ injects a set $B$ if $|A+B| = |A||B|$, and let $I(B) = \max \{|A| :A\text{ injects } B\}$.
For a subgroup $H$, it is well-known that $I(H) = |...
- 3,499
6
votes
0
answers
123
views
Sets $X,Y$ of natural numbers such that any natural $n$ writes uniquely $n=x+y$ [duplicate]
There are many pairs $X, Y$ of infinite subsets of $\mathbb{N}:=\{0,1,2\dots\}$ such that any $n\in\mathbb{N}$ writes uniquely as $n=x+y$, with $x\in X$ and $y\in Y$. An example of such a pair is $(X,...
- 60.5k
12
votes
1
answer
307
views
Partition of [3n] into summoids
Let $ [n] $ be the set $ \{1,2,\ldots n\}$.
A summoid is a subset $ A \subset [n] $ of the form $ \{a,b,a+b\} $ (you can choose a better name, if it doesn't exist already).
Now, I developed by ...
2
votes
2
answers
393
views
Playing leapfrog with primes
In connection with how primes jump (How do these primes jump?),
I consider the following game.
Let $R$ be a finite set of positive integers. For this question, I content myself with $R$ being the $k$ ...
- 13k
17
votes
1
answer
701
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 $...
- 422
4
votes
0
answers
546
views
The original proof of Szemerédi's Theorem
Nowadays there are plenty of different proofs of the celebrated Szemerédi's Theorem but for historical reasons I would like to read and understand the original proof. The proof is very tricky and, for ...
- 1,561
9
votes
0
answers
297
views
An abstract zero-sum problem
I would like to know whether the problem described below has appeared in the literature and/or whether similar questions have been studied. I would be very happy to find some references or, if none ...
- 1,169
8
votes
1
answer
571
views
Subsets of [1..N] with no three-term arithmetic progressions and no large gaps
Let S be a subset of [1..N] containing no three-term arithmetic progression, and let h(S) be the size of the largest gap between two consecutive elements of S. By Roth's theorem, h(S) has to grow ...
- 19.2k
4
votes
2
answers
784
views
asymptotic for restricted partitions
Let $m$ and $n$ be two positive integers and denote by $P(n,m)$ the number of partitions of $n$ into $m$ non-negative integers.
Is there an asymptotic formula for $P(n,m)$ ?? Any reference is welcome....
- 2,384
4
votes
2
answers
763
views
How local the property of "being a partition" is?
Note: The problem is solved! See EDIT below.
The following question about integer partitions arose from a purely "practical" question: Does there exist better dynamic programming algorithms for the ...
- 213
6
votes
1
answer
452
views
Bounds on the size of sets not containing a given finite pattern
Recall the following version of Szemerédi's Theorem: let $r_k(N)$ be the largest cardinality of a subset of $[N]:=\{1,\ldots, N\}$ which does not contain an arithmetic progression of length $k$. Then, ...
- 4,660
11
votes
2
answers
826
views
Sums of subsets of $\mathbb{Z}/n\mathbb{Z}$
I have encountered a problem that I suspect has been thoroughly studied but I have not been able to find references. Can anyone point me to a published reference dealing with this or a closely related ...
- 2,851
5
votes
1
answer
360
views
Is the generalized Erdős–Heilbronn problem true for finite cyclic groups?
The generalized Erdős–Heilbronn (GEH) theorem, which is proved by da Silva and Hamidoune in 1994, states that:
Theorem. If p is a prime and $X$ is a subset of $\mathbb{Z}_p$, then $|\hat{k}X| \geq \...
- 1,250
4
votes
2
answers
592
views
Sum of sets modulo a square
I would be glad to see a reference to the following easy lemma in additive combinatorics: if $A_1$ and $A_2$ are two sets of remainders modulo $n^2$, each has cardinality $n > 1$ and all elements ...
- 109k