All Questions
Tagged with co.combinatorics additive-combinatorics
330 questions
1
vote
1
answer
21
views
Maximum density of sum-free sets with respect to Knuth's "addition"
A subset $S\subseteq\mathbb{N}$ is said to be sum-free if whenever $s,t\in S$, then $s+t\notin S$. For instance the set of odd numbers is sum-free and has (lower and upper) asymptotic density 1/2.
...
- 48.8k
1
vote
1
answer
324
views
Want to show that this sum vanishes modulo p
Let $p\ge 5$ be a prime number, and consider the following sum:
\begin{align}
S &= \sum_{v_0 = 1}^{p - 2} \binom{p - 2}{v_0} \, \theta^{v_0 - 1}(Y) \cdot \theta^{p - 2 - v_0}(Y) \\
&+ \frac{1}{...
- 29
4
votes
1
answer
148
views
Lower bounding a sumset quantity
Given $A,B \subset[0,...,d]^n$ such that $A \cap B = \phi$. Can we show
$$ |(2A \cup 2B) \triangle (A + B)| \geq \Omega_d({\rm poly}(|A|,|B|))$$
where $2A = A+A, 2B = B+B$ and we are taking the ...
- 341
5
votes
0
answers
185
views
Gaps in sumsets and difference sets
a) Let $S\subset \{1,2,\dotsc,N\}$ be a fairly thick set (with at least $N^{1-\epsilon}$ elements, say). Suppose that the intersection of, say,
$$3 S - 3 S = \{a_1+a_2+a_3-(a_4+a_5+a_6): a_1,\dotsc,...
- 20.2k
3
votes
1
answer
168
views
Maximal zero-sum free sequences of $C_3^n$
I am working on the Davenport constant for groups, $D(G)$, which is the minimal number $d$ such that every sequence or multiset of $d$ elements of the group $G$ always contains some non-empty zero-sum ...
2
votes
0
answers
187
views
Matrix with elementary symmetric polynomials as entries
Let $n\geq 1$, and for each $j=1,\ldots, n+1$ let $\mathbf{X}_{j}=(X_{j1},\ldots, X_{jn})$ be $n$ variables. Let $M$ be the $(n+1)\times (n+1)$ matrix whose $(i,j)$-th entry is $$M_{ij}=(-1)^i e_{i-1}(...
2
votes
0
answers
62
views
Maximum distance between consecutive terms in sequence with arbitrarily long APs
Good evening. I am writing a paper on complex analysis, and as a corollary (of my work and others'), I believe that I have managed to deduce the following result.
Proposition: Let $n_1 < n_2 \cdots ...
- 121
0
votes
1
answer
53
views
Square submatrix of a binary matrix with all columns having the same sum
Let $M$ be a $m \times n$ matrix with binary entries (i.e. a matrix all whose entries belong to the set $\{0,1\}$), with $m\geq n$. Suppose each row of $M$ contains exactly $k$ ones. Given $n$ ...
2
votes
1
answer
232
views
Is the small Davenport constant for $S_n$, $d(S_n)=n(n-1)/2$?
The Davenport constant $D(G)$ of a finite group $G$ is the minimal $d$ such that any sequence/multiset of length $d$ is one-product, i.e., identity can be obtained as a product (in some order) of some ...
0
votes
0
answers
164
views
One-product free sequences for $A_n$
I am working on computing the Davenport constant $D(G)$ for $S_n$ and $A_n$, i.e., the minimal number $d$ such that every sequence (multiset) of $d$ elements contains some subsequence giving identity ...
3
votes
1
answer
259
views
Davenport constant $D(S_5)=10$ or $11$?
I am working on computing the Davenport constant $D(G)$
of symmetric groups, which is the minimal number $d$
such that every sequence of $d$
elements, possibly with repetitions, is one-product, i.e. ...
3
votes
0
answers
155
views
Correspondence between even and odd permutations in $S_5$
I am working on the Davenport constant for symmetric groups, $D(G)$
, which is the minimal number $d$
such that every sequence of $d$
elements in the group G
is one-product sequence, i.e, we can ...
2
votes
1
answer
169
views
The number of small sum-free subsets of $[n]$
I'm interested in the following question:
Can we bound the number of sum-free subsets of size $k$ of $\{1,2,\dots,n\}$, as a function of $n$ and $k$? In particular, what can we say about a function $...
- 541
7
votes
0
answers
176
views
Sumsets that contains many squares, Improvement on the bound
I'm being troubled by this problem on AoPS:
https://artofproblemsolving.com/community/c6h1998237p13955033
I searched for any literature related to it such as
Nguyen, Hoi H., and Van H. Vu., Squares ...
- 63
3
votes
0
answers
111
views
Ruzsa embedding lemma in $\mathbb{F}_p^N$
Below, you will find the lemma known as the Ruzsa embedding lemma in $\mathbb{F}_p^N$. I understood the idea of the proof quite well, but one technical detail is bothering me. I've pondered it for a ...
- 330
1
vote
0
answers
164
views
Combinatorial question related to Hankel-type matrices
Let $\mathbb{N}$ be the set of non-negative integers. Let $n\geq 2, d$ be positive integers. I would like a lower bound on the largest integer $r$ for which the following property holds:
For any ...
- 980
5
votes
0
answers
307
views
On $s$-additive sequences
For a non-negative integer $s$, a strictly increasing sequence of positive integers $\{a_n\}$ is called $s$-additive if for $n>2s$, $a_n$ is the least integer exceeding $a_{n-1}$ which has ...
- 791
3
votes
2
answers
224
views
Unique "clique" of differences in $\mathbb{Z}/m\mathbb{Z}$
Are there absolute constants $0 < \epsilon < 1$ and $N \in \mathbb{N}$ such that the following holds: For every $m \in \mathbb{N}$ and every $A \subseteq \mathbb{Z}/m\mathbb{Z}$ with $\frac{\...
- 73
1
vote
0
answers
99
views
Szemeredi Regularity Lemma - Reasonable Bounds
Recently, I came across the wonderful Szemeredi regularity lemma and I was wondering. Are these "natural/reasonable/standard" examples of random graphs families, for which the number of $\...
- 5,405
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
5
votes
2
answers
691
views
Representing natural numbers as sums of distinct prime powers
I am investigating whether every natural number $n > 18$ can be represented as a sum $p_1^{m_1} + \dots + p_k^{m_k}$, where $p_1, \dots, p_k$ are distinct primes, and $m_1, \dots, m_k$ are distinct ...
- 1,228
0
votes
1
answer
54
views
Bounding maximum sum of integer matrix entries in a non-attacking rook placement
Let $A =(a_{ij})$ be a $m \times n$ matrix with nonnegative integer entries bounded above by $k$. To find the set of entries of $A$ in a non-attacking rook placement such that the sum $S$ of them is ...
- 223
5
votes
1
answer
297
views
Expected number of coin flips before you see a $k$-term arithmetic progression of heads
Let $\{X_i\}_{i \in \mathbb Z_+} $ be independent fair coin flips. Write $S := \{i \in \mathbb Z_+\, | \, X_i \text{ is heads}\}$, and define, for an integer $k \geq 3$,
$$Y := \inf \{n \in \mathbb N \...
- 6,155
0
votes
0
answers
82
views
High probability bound on number of sparse solutions to Gaussian linear system
Suppose we have a random matrix $A \in \mathbb{R}^{m \times n}$ with all entries i.i.d. from the standard Normal distribution $\mathcal{N}(0, 1)$. Suppose $k$ divides $n$, and let $S \subseteq \mathbb{...
- 43
6
votes
2
answers
1k
views
Acyclic matching property in $\mathbb{Z}/p\mathbb{Z}$
Let $B$ be a finite subset of the group $G$ which does not contain the neutral element. For any subset $A$ in $G$ with the same cardinality as $B$, a matching from $A$ to $B$ is defined to be a ...
- 429
0
votes
0
answers
180
views
Upper bound of number of different rows for a binary matrix
Let $\mathcal{X} \subseteq \mathbb{R}^n$ be a measurable space, Fix $m,q \in \mathbb{N}^*$, (the $m$ $x_i$'s are i.i.d and follow distribution $\mathcal{D}$)
and $X = (x_1, \dots, x_m) \sim \mathcal{D}...
- 29
3
votes
2
answers
493
views
Why can we not find exact values for sizes of cap sets for $d>6$?
I've been reading about cap sets in $\mathbb{F}_3^d $ over the past couple of days and wondered why we can only find bounds, as opposed to exact values, for (maximum) sizes of cap sets for $d>6$. ...
- 41
1
vote
0
answers
76
views
subsets of $\mathbb{N}$ whose shifts have finite intersection property in density
I am interested in proving the statement:
Let $S\subseteq\mathbb{N}$ such that for every $r\in\mathbb{N}$ and for every $k_{1}$, $k_{2}$, $\ldots$, $k_{r}\in\mathbb{N}$, the set $\big(S-k_{1}\big) \...
- 119
16
votes
2
answers
1k
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$. ...
- 791
2
votes
1
answer
249
views
Structural description of Bohr sets in $\mathbb{Z}_N$
Definition 1. Let $\Gamma\subset \widehat{G}$ and $\delta\in [0,2]$. The Bohr set with frequency set $\Gamma$ and width $\delta$ is the set $\text{Bohr}(\Gamma; \delta)= \big\{x\in G: |\chi(x)-1|\leq \...
- 330
8
votes
1
answer
442
views
When can $L$ sets of the form $\{a,b,a+b\}$ partition $\{1,2,\dots, 3L\}$?
Firstly, this question has been posted to Math StackExchange with no complete answer so far.
Consider a set of the form $\{a,b,a+b\}$ where $a$ and $b$ are positive integers with $b > a$. I will ...
0
votes
1
answer
164
views
Upper bounds estimates of Minkowski sum
Let $A,B \subset \{0,...,d\}^n$, do we have any result that says $|A+B| \leq \mathcal{O}_d(|A|\cdot |B|)^\tau$ for $\tau < 1$. The case $\tau = 1$ is trivial, and due to the restricted setting, I ...
- 341
5
votes
1
answer
1k
views
Estimate of Minkowski sum
Let A $\subset [0:2]^n$, where $[0:2]=\{0,1,2\}$, then define $2A= \{ a+b\mid a,b \in A \}$. I wanted to know the best known lower-bound estimates for $|2A|$.
I intuitively expect that $|2A| \geq |A|^{...
- 341
15
votes
2
answers
750
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....
- 153
1
vote
1
answer
200
views
Instance of polynomial van der Waerden without good bounds
Let $P\subset \Bbb{Z}[X]$ be a finite set of polynomials with constant-term zero. Then, polynomial vdW says:
For eacg finite $r$, there exists some $N=N(P,r)$, such that every $r$-coloring $C:\{1,\...
- 3,499
5
votes
1
answer
369
views
Primitive recursive bounds for multidimensional polynomial vdW / HJ
In Shelah's paper 679, he proves primitive recursive bounds for the polynomial Hales-Jewett theorem and thus for the polynomial van der Waerden theorem.
How about for the multidimensional polynomial ...
- 383
1
vote
1
answer
348
views
Khovanskii's theorem on iterated sumsets
I was watching Gowers video lectures "Introduction to Additive Combinatorics" (my question is about the statement he made at the 21st minute) and came across wonderful theorem due to ...
- 330
1
vote
0
answers
129
views
The number of incidences between points and parabolas on $\mathbb{R}^2$
I was reading Adam Sheffer's book "Polynomial Methods and Incidence Theory" and I tried to solve the following exercise:
Exercise 1.1 Construct a set $\mathcal{P}$ of $m$ points and a set $\...
- 330
0
votes
0
answers
218
views
Equivalent formulation of Szemerédi-Trotter theorem
I am reading the first chapter of Adam Sheffer's book "Polynomial Methods and Incidence Theory" and in Lemma 1.15 he proves an equivalent formulation of Szemerédi-Trotter theorem. Before ...
- 330
1
vote
1
answer
332
views
Szemerédi–Trotter type theorem in finite field
This question is about the content of this paper by J. Bourgain, N. Katz, T. Tao.
In the final step (page 18) of the proof of Szemerédi-Trotter type theorem, we have already known
$$|A''+A''|\lesssim ...
- 13
5
votes
1
answer
151
views
Beating trivial bound for $k$-AP-free sets in characteristic $k$
Given integers $k,n\ge 1$, I shall write $\Bbb{Z}_k^n := (\Bbb{Z}/k\Bbb{Z})^n$.
Fix $k\ge 3$. Let $r_k(\Bbb{Z}_k^n)$ denote the cardinality of the largest $A\subset \Bbb{Z}_k^n$, such that $A$ does ...
- 3,499
2
votes
0
answers
189
views
Component-wise sums of permutations
Given a set $S$ containing all possible permutations of a vector $v = (1, 2, 3, ..., n-1, n)$, find the size of the set $P$, where $P$ is defined as the set of possible component-wise sums obtained by ...
- 21
3
votes
0
answers
140
views
Counting $A+A-A$ with partial multiplicity
A recent question asked whether, given a finite set of positive numbers $A$, it is always the case that the set $A+A-A$ has more positive than negative elements. Terry Tao showed that this is false (...
- 6,001
59
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 ...
- 643
2
votes
0
answers
96
views
Trapezoid-free subsets of the plane obtained by deleting lines
Let $A,B,C \subseteq \mathbb{Z}_n$. Suppose that for any $a' \in A, b' \in B, c' \in C$,
\begin{align*}
|(A+b') \cap (B+a') \cap -C| &\le 1,\\
|(A+c') \cap -B \cap (C+a')| &\le 1,\\
|-\hspace{-...
- 539
3
votes
0
answers
187
views
Szemerédi’s theorem in really dense sets
This question is inspired by Tao’s answer in this post. I have thought about this occasionally for several months without anything concrete.
Question:
Given $\delta>0$ and $k\ge 3$, let $N= N_k(\...
- 3,499
8
votes
1
answer
304
views
The growth rate of a commutator set in a non-elementary group
Let $G$ be a non-elementary group generated by a finite set $S$. Here, a group is called non-elementary if it is not virtually abelian. Denote $S^{\le n}:=\{g\in G: |g|_S\le n\}$ for any $n\in \mathbb ...
- 145
1
vote
0
answers
170
views
A representation problem involving strict partition numbers
For each positive integer $n$, let $q(n)$ denote the number of ways to write $n$ as a sum of distinct positive integers. We call those $q(n)\ (n=1,2,3,\ldots)$ strict partition numbers.
The sequence $...
- 15.6k
14
votes
2
answers
1k
views
A sum-product phenomenon on reciprocals
Let $A \subset \mathbb F_p \setminus \{0\} $ and let $A+1/A = \{x+1/y:x,y \in A\}$.
Question: For fixed $c>0$, if $|A| \geq cp$, is $|A+1/A|$ at least $(1-o(1))p$ when $p \rightarrow \infty$?
Known:...
- 9,501
2
votes
0
answers
94
views
On fractional parts and Behrend’s construction
Given $\theta \in \Bbb{T}^D := \Bbb{R}^D/\Bbb{Z}^D$, write $f_\theta$ for the homomorphism from $\Bbb{Z}\to \Bbb{T}^D$ induced by $1\mapsto \theta$.
For $x\in \Bbb{T}^D$, let $||x||$ be the smallest $\...
- 3,499